Attributed Graph Clustering with Dual Redundancy Reduction

1 Introduction

Deep clustering methods, which improve the performance of complicated clustering problems with the help of deep network architecture, have achieved significant progress on applications like semantic segmentation [Caron et al., 2018], social network analysis [Zhong et al., 2016], and face recognition [Schroff et al., 2015]. However, the successes of these methods are mostly rooted in the advances of autoencoder [Guo et al., 2017; Xie et al., 2016], convolutional neural networks, and generative adversarial networks [Xu et al., 2019], which are not applicable to the non-Euclidean graph datasets. However, structural information is also found essential for data analysis [Zhang et al., 2021]. As a consequence, graph convolutional network (GCN) [Kipf and Welling, 2016a] based clustering algorithms, for example, deep attentional embedded graph clustering (DAEGC) [Wang et al., 2019] and deep fusion clustering network (DFCN) [Tu et al., 2021], are recently attracting increasing attention.

∗Corresponding author

Nevertheless, the above GCN-based methods learn node representation by adopting the graph structure reconstruction principle, which may ignore the subtle but essential relationships and lead to indiscriminative representation among samples [Suresh et al., 2021]. The problem is especially severe in the unsupervised learning scenario. Consequently, graph contrastive learning (GCL), which focuses on maximizing mutual information (InfoMax) between representations of the same instance with different augmentations, is proposed to alleviate the problem [Velickovic et al., 2019; Zhao et al., 2020]. It has achieved considerable improvement in node embedding and clustering. By utilizing two decoupled GCN-based encoders, multi-view graph representation learning (MVGRL) [Hassani and Khasahmadi, 2020] conducts cross-view contrastive learning to facilitate invariant node embedding learning. Although good performance has been achieved, the InfoMax principle is found to risk capturing task-unrelated information, which is also able to satisfy InfoMax [Tschannen et al., 2019] and lead to sub-optimal node representation. To solve the problem, adversarialGCL [Suresh et al., 2021] integrates information bottleneck theory (IB) [Tishby et al., 2000] with self-supervised GCNs by an adversarial learning mechanism to reduce redundant information in graph-structure data for graph-level tasks. However, it ignores the node-level redundancy reduction. Motivated by decreasing redundant information in node clustering tasks, we propose attributed graph clustering with dual redundancy reduction (AGC-DRR) to reduce the information redundancy both in input space and latent feature space. Specifically, for the input space redundancy reduction, we introduce an adversarial learning mechanism to adaptively learn a redundant edge-dropping matrix to ensure the diversity of the compared sample pairs with the anchor of the original graph. Subsequently, to reduce the redundancy in latent space, we force the correlation matrix of the cross-augmentation sample embedding to approximate an identity matrix. Consequently, the learned network is more robust against perturbation while discriminative against different samples. In Fig. 1, we compare the discriminative capability of GAE and our proposed AGC-DRR by calculating the cosine similarity matrices in the learned latent space, respectively. As we can see, when adopting the same encoder structure, the discriminative capability of the sample embedding is largely improved by our proposed dual redundancy reduction mechanism. We list the contributions of this paper as follows:

• AGC-DRR is the first attributed graph clustering algorithm that adaptively learns the adjacent matrix with an adversarial learning mechanism to the best of our knowledge.
• We propose a dual redundancy reduction strategy that decreases the information redundancy in both the input space and latent feature space to improve clustering performance.
• AGC-DRR is free from pre-training, which makes the algorithm efficient and more stable.
• Extensive experimental results have demonstrated that

AGC-DRR outperforms the state-of-the-art clustering methods on most of the compared datasets.

2 RelatedWork

2.1 Deep Graph Clustering

A proper self-supervised principle is essential for deep clustering methods. Following the auto-encoder framework, graph auto-encoder (GAE) and variational graph autoencoder (VGAE) [Kipf and Welling, 2016b] learn node representations by reconstructing the adjacent matrix. Deep attentional embedded graph clustering (DAEGC) [Wang et al., 2019] integrates GCNs with a self-attention mechanism to capture more informative relationships among nodes. Also, adversarially regularized graph auto-encoder (ARGA) [Pan et al., 2020] introduces an adversarial learning mechanism into GAE to improve the quality of learned representation. The mentioned methods improve the clustering performance by carefully exploiting the structural information, other methods like SDCN [Bo et al., 2020] and DFCN [Tu et al., 2021] achieve the target through learning both the attribute and structural information. Specifically, they combine the autoencoder and GAE with a carefully designed mechanism for more comprehensive information merging. Moreover, different from the above methods, deep graph infomax (DGI) [Velickovic et al., 2019] learns node embedding with an InfoMax principle. After that, various GCL-based algorithms are proposed by maximizing mutual information between representations of the same instance with different augmentation methods [Zhao et al., 2021; Hassani and Khasahmadi, 2020]. However, the graph structural augmentation strategy in most existing GCL-based methods is pre-defined edge perturbation, which can not be optimized and is separated from representation learning and clustering task. To have the augmentation better serve the task of graph clustering, we design a special sub-network to learn the structure augmented graph adaptively. The learning processes of graph structure and clustering are united into a common adversarial optimization framework.

2.2 InformationMaximization Principle

Driven by the great success of contrastive learning (CL) of CNN-based methods in computer version scenarios, great progress has also been witnessed in the field of unsupervised graph learning. Specifically, GCL applies CL on graphs to capture subtle relationships for high-quality node representation and clustering performance improvement. The trailblazing work DGI [Velickovic et al., 2019] proposes to obtain node representations by maximizing mutual information [Hjelm et al., 2018] between the local patch and global summary of a graph. Further, mutual information is developed into graphs with contrastive augmented pairs generated by edge-dropping or edge perturbation [Zhao et al., 2020]. However, researchers have found that the InfoMax principle could put the corresponding algorithm at the risk of collecting too much trivial and downstream task-irrelevant information for over-accurate node recognition [Suresh et al., 2021]. As a consequence, information bottleneck (IB) theory [Tishby et al., 2000], which aims to obtain minimal sufficient information for downstream tasks, is taken into consideration to avoid this issue. Graph information bottleneck (GIB) [Wu et al., 2020] applies IB for graph representation learning and then GIB is used in [Yu et al., 2020] to address subgraph recognition problem.

3 Method

In this section, we will introduce the proposed attributed graph clustering with dual redundancy reduction (AGCDRR) algorithm, which unifies the graph structural augmentation and sample clustering into a common min-max optimization framework to reduce the information redundancy in both input and latent feature spaces. As shown in Fig. 2, AGC-DRR mainly consists of two components, i.e., structure augmented sub-network (N1) and clustering sub-network (N2). Next, we will first introduce the basic notations and preliminaries, and then introduce N1 and N2 in detail, respectively.

3.1 Basic Notations

Given an undirected graph G = {E, V} with K categories, where E and V = {v1, v2, . . . , vN} are the corresponding edge set and node set, M = |E|, N = |V|. X ∈ RN×d is the node attribute matrix and d is the raw attribute dimension. A ∈ RN×N is the original adjacent matrix, Aij = 1 denotes that there exists a connection between node vi and node vj, otherwise, Aij = 0. The notations are summarized in Table 1.

3.2 Preliminaries

Graph Encoder As shown in Fig. 2, the GCN-Encoder is a three-layer graph convolutional network (GCN) [Kipf and Welling, 2016a] that aggregates the first-order neighbor information to update the embedding of the central node for representation learning, which is formulated as below:

where ¯A ∈ RN×N denotes the normalized adjacent matrix, D = diag(d1, d2, . . . , dN) ∈ RN×N is a degree matrix, dn = ∑Nj=1 Anj, and I ∈ RN×N is an identity matrix. Z(l) ∈ RN×d(l) and H(l) ∈ Rd(l-1)×d(l) denote the latent representations and network parameters of the l-th layer, respectively. σ denotes the Tanh activation function.

Graph Contrastive Learning Different from the autoencoder-based methods [Kipf and Welling, 2016b; Wang et al., 2019] that learn node representations by reconstructing the graph structure, graph contrastive learning (GCL) aims to maximize the agreement between positive sample pairs and minimize the agreement between negative sample pairs. To this end, mutual information maximization (InfoMax) [Hassani and Khasahmadi, 2020] is a commonly adopted measure to estimate the agreement between sample pairs. The graph contrastive learning objective is generally formulated as:

where I(·, ·) and sim(·, ·) denote the mutual information and the cosine similarity, respectively. Z1 ∈ RN×d′ and Z2 ∈ RN×d′ are two-view graph embeddings learned from the corresponding views, z1 i and z2 i refer to the i-th rows in Z1 and Z2 , respectively.

3.3 Clustering Sub-network

Most existing GCL-based clustering methods focus on learning node representations by maintaining the consistency of the latent feature spaces of different views as Eq. (3) and then utilizing classic clustering algorithms (e.g., K-means [Wong, 1979]) to obtain the clustering results over the learned representations. In this circumstance, the optimization processes of representation learning and node clustering are disconnected, thus leading to sub-optimal clustering performance. To solve this issue, we develop a one-step clustering subnetwork that can directly predict the probabilities of clusterID for each sample. Specifically, after obtaining the graph embeddings of both views, we transform them into a Kdimension clustering space by feeding Z1 and Z2 into a 1layer Multi-layer Perception (MLP) with a softmax activation function, where K refers to the number of clusters. The above learning process is formulated as:

where Cv ∈ RN×K denotes the clustering indicator matrix in the v-th view. To maintain the consistency of two-view clustering spaces, we reformulate the Eq. (3) from the perspective of the sample level as below:

Algorithm 1 The training procedure of AGC-DRR

Input: Graph data {A, X}; Number of clusters K; Maximum iterations T ; Hyper-parameter λ Output: Clustering results

• 1: for t = 1 : T do
• 2: CalculateWand ˜A to obtain the structure augmented graph by Eq. (9) and Eq. (10), respectively; /∗ Fix N2 and optimize N1∗/
• 3: Calculate C1 and C2 by Eq. (4);
• 4: Update N1 by minimizing the objective in Eq. (11). /∗ Fix N1 and optimize N2∗/
• 5: Calculate Z1 and Z2 by Eq. (1);
• 6: Calculate C1 and C2 by Eq. (4);
• 7: Update N2 by maximizing the objective in Eq. (12).
• 8: end for
• 9: Obtain clustering results over the average of C1 and C2
• 10: return Clustering results

where c1i and c2i are the i-th rows in C1 and C2 , respectively. To improve the robustness of the clustering subnetwork against the perturbation derived from other components, we further consider the consistency from the perspective of cluster level via Eq. (6):

where c1j T and c2j T are the j-th columns in C1 and C2 , respectively. In this way, both the similarities of clustering assignments for the same instance and node distributions in the two views are considered to optimize this sub-network to further improve the clustering performance. The total mutual information between two views is formulated as:

Latent Space Redundancy Reduction Although the InfoMax principle plays a crucial role in GCL-based methods for performance improvement, it risks enabling the encoder to capture redundant information when estimating the agreement of sample pairs. To alleviate this issue, we introduce a redundancy reduction strategy into the latent space by forcing the cross-view correlation matrix to approximate an identity matrix:

This term reduces the redundancy across two-view embeddings within the corresponding graphs. By this means, redundant information in the embedding could be minimized and more discriminative features could be well preserved. Hence, it makes the learned representations be affected less by irrelevant information, thus guaranteeing the quality of latent space for subsequent clustering tasks.

3.4 Structure Augmented Sub-network

In existing GCL-based methods, edge perturbation is a commonly adopted graph augmentation before network learning, and the augmented graph is generally viewed as the ground truth information in a fixed pattern. Since the augmented graph is stemmed from the original graph, it would contain some incorrect or redundant connections. If these noisy structures are not eliminated in the network learning process, the learned clustering space would inherit it in the final step. To tackle this problem, we design a structure augmented subnetwork to learn a clustering-oriented structural graph, which would adaptively learn a redundant edge-dropping matrix to ensure the diversity of the compared sample pairs.

Edge Weight Learner As shown in Fig. 2, there exists an additional GCN-Encoder in N1 that has an identical architecture as the one in N2. Similarly, this graph encoder accepts the normalized adjacent matrix ¯A and the node attribute matrix X as input and outputs the graph embedding Z ∈ RN×d′ . The learned graph embedding Z is first adopted to generate the edge embedding E = {E1, E2, . . . , EM} ∈ RM×2d′ , where Em = C(zi, zj), C(·, ·) is a concatenation operation, zi and zj are the embeddings of central node vi and neighbor node vj. Then the resultant edge embedding E is fed into a 1-layer MLP with sigmoid activation function to obtain the edge-oriented weight vector W = [w1, w2, . . . , wM]T ∈ RM×1 as Eq. (9):wi = sigmoid(MLP(Ei)), (9)

where wi means the probability of the corresponding original edge ei being preserved in the augmented graph. Accordingly, 1 -wi denotes the edge-dropping probability.

After that, we transform the weight vector W ∈ RM×1 into an edge-oriented weight matrix W′ ∈ RN×N to generate the structure augmented graph G ′ . Specifically, we fill W′ ij with wm if node vi and node vj are connected via the edge em in the original graph, otherwise, W′ ij is set to zero value. The construction of augmented adjacent matrix ˜A is formulated as follows:

where ⊙ is the Hadamard product, i.e., ˜Aij =W′ ij × ¯Aij. Thus, the final augmented graph G ′ consists of the augmented adjacent matrix ˜A and the node attribute matrix X.

By minimizing Eq. (7), the structure augmented subnetwork is enabled to reduce the redundant information in the input space to ensure the diversity of the compared sample pairs. In this way, the learning processes of graph structure and clustering are united into a common adversarial optimization framework, which could make both sub-networks benefit each other to alleviate the risk of information redundancy for better clustering.

Regularization Term To filter the redundant information as much as possible, we introduce a regularization term 1M ∑Mi=1 wi into Eq. (7) to control the ratio of structure information preservation and reduction, where wi refers the probability that i-th edge gets preserved.

In summary, the final objective function for N1 and N2 can be formulated as Eq. (11) and Eq. (12), respectively.

where λ is a pre-defined hyper-parameter. The training procedure of AGC-DRR is presented in Algorithm 1.

4 Experiment

4.1 Experiments Setup

Benchmark Datasets We evaluate the proposed AGCDRR on four public benchmark datasets including ACM 1 , DBLP 2 , CITE 3 , and AMAP [Shchur et al., 2018]. The brief descriptions of these datasets are summarized in Table 2.

Training Details We conduct experiments to evaluate the proposed AGC-DRR on the PyTorch platform with the NVIDIA GeForce RTX 3080. Within an adversarial learning framework, N1 and N2 are optimized by minimizing Eq. (11) and maximizing Eq. (12), respectively, and they are trained alternately. We train AGC-DRR on all benchmark datasets for at least 100 iterations until convergence. In the testing phase, we calculate the average of both clustering indicator matrices, i.e., C1 and C2 , and directly predict the cluster-ID for each sample using a softmax function. To avoid the adverse effect of randomness, we run each experiment 10 times and report the average values with standard deviations.

Evaluation Metrics Here we adopt four public metrics to evaluate clustering performance for all compared methods, including Clustering Accuracy (C-ACC), Average Rand Index (ARI), Normalized Mutual Information (NMI), and macro F1-score (F1).

Parameter Settings For MVGRL and ARGA/ARVGA methods, we reproduce the official source code by following the parameter settings of their original papers and report the corresponding clustering results. For other compared methods, we directly record the clustering results reported in DFCN [Tu et al., 2021]. For our proposed AGC-DRR, we optimize it with the Adam optimizer, the learning rates for N1 and N2 are set to 1e-3 and 1e-4 on CITE, and 1e-4, 5e-4 on others, respectively. The regularized hyper-parameter λ is set as 1 for all datasets.

4.2 Clustering Results and Analysis

To verify the superiority of AGC-DRR, we compare it with 13 clustering methods, including 1) one classic clustering method: K-means [Wong, 1979]; 2) three deep neural network (DNN)-based clustering methods: AE [Hinton and Salakhutdinov, 2006], DEC [Xie et al., 2016], and IDEC [Guo et al., 2017]; and 3) nine graph neural network (GNN)-based clustering methods: GAE/VGAE [Kipf and Welling, 2016b], ARGA/ARVGA [Pan et al., 2020], DAEGC [Wang et al., 2019], MVGRL [Hassani and Khasahmadi, 2020], DFCN [Tu et al., 2021], and SDCN/SDCNQ [Bo et al., 2020].

1 https://dl.acm.org/

2 https://dblp.uni-trier.de

3 http://citeseerx.ist.psu.edu/index

Table 3 presents the clustering performance comparison of all compared clustering algorithms. From these results, we can observe that 1) compared with the early clustering methods that exploit the node attributes but ignore the structure information, i.e., K-means, AE, DEC, and IDEC, AGC-DRR outperforms them by a large margin, these results indicate that the structure information among data samples is significant to learn more discriminative node representations; 2) AGC-DRR also achieves competitive performance on most datasets compared with GNN-based methods that consider both attribute and structure information for clustering. Taking the metric F1 for instance, it exceeds DFCN by 1.75%, 4.20%, 0.52%, and 1.14% performance increments, respectively. This is because that AGC-DRR considers reducing the redundant information in both input and latent feature spaces, thus the network is enabled to learn a clustering-friendly graph augmentation as well as discriminative latent representations. In addition, for the less satisfying performance on the CITE dataset, we think the reason is that the attribute information of CITE plays a more important role than its structural information in the performance of clustering which may be caused by a higher attribute dimension. Since DFCN and MVGRL have extra architectures to extract attribute information, the attribute embeddings of these methods are better learned. However, AGC-DRR is more balanced, it provides more stable performance overall for four compared datasets.

4.3 Ablation Studies

In this section, we conduct ablation studies to verify the superiority of each component in our method. The w/o minmax method and the w/o LMSE method indicate the network with the proposed min-max optimization mechanism and the MSE objective being removed, respectively. From the results in Table 4, some observations can be summarized. AGC-DRR exceeds the method w/o minmax by 0.6%, 15.6%, 4.4%, and 4.7% accuracy increments, and exceeds the method w/o LMSE by 6.9%, 22.4%, 7.3%, and 5.9% accuracy increments on ACM, DBLP, CITE, and AMAP, respectively. These results demonstrate that both components play an essential role in our method for improving the clustering performance. On the one hand, the min-max optimization mechanism could reduce the redundant information in the input space to ensure the diversity of the compared views for a more reliable structure augmented graph. On the other hand, LMSE could achieve latent space redundancy reduction to obtain more discriminative node representations. Both components contribute to better clustering performance.

4.4 Effect of Different Graph Structure

To verify the robustness of AGC-DRR, we utilize three types of adjacent matrices as input. In our settings, ADJ indicates the normalized adjacent matrix ¯A. RW indicates the adjacent matrix constructed by random walk [Grover and Leskovec, 2016]. PPR indicates the adjacent matrix constructed by Personalized PageRank algorithm [Hassani and Khasahmadi, 2020]. As illustrated in Fig. 3, these clustering results on two benchmark datasets have clearly verified that AGC-DRR could achieve robust performance when adopting different adjacent matrices.

4.5 t-SNE Visualization

As illustrated in Fig. 4, we present the clustering results of different clustering methods on ACM and DBLP by t-SNE algorithm [Van der Maaten and Hinton, 2008]. From these figures, we observe that the proposed AGC-DRR can clearly reveal the intrinsic clustering structure among samples.

5 Conclusion

In this paper, we design a novel attributed graph clustering with dual redundancy reduction (AGC-DRR), which can reduce the redundant information in both input and latent feature spaces. In the proposed method, the learning processes of structure augmented graph and clustering are united into a common min-max optimization framework. In this way, the learned network is robust against perturbation while discriminative against inter-class samples. The proposed AGC-DRR has been evaluated on four benchmark datasets. Extensive experimental results verify that our proposed method outperforms state-of-the-art counterparts.

Acknowledgments

This work is supported by the National Key R&D Program of China (2020AAA0107100), the National Natural Science Foundation of China (Grant No. 61922088, 62006237).