Redundancy-Free Self-Supervised Relational Learning for Graph Clustering

Recent years have witnessed great progress in Graph Neural Networks (GNNs) and achieved state-of-the-art performance. The concept of GNNs was proposed [29] before 2010 and has become an ever-increasing theme. A general paradigm of GNNs is to iteratively update node representations by aggregating neighboring information based on message-passing [30]. Representative method Graph Convolutional Network (GCN) [31] extended the classical convolutional neural networks to the case of graph-structured data. Subsequent work Graph Attention Network (GAT) [32] further leveraged the attention mechanism [33] to dynamically aggregate the features of neighbors. With the powerful capability of GNNs, the learned graph representations can be used to serve a variety of downstream tasks, such as node classification [31, 34], graph classification [35, 36, 37], and graph clustering [18, 38].

The goal of deep clustering focus on utilizing the excellent representation ability of deep learning to serve the clustering process, which has achieved remarkable progress. Existing methods can be categorized into three main groups based on the training objectives: (i) reconstruction based methods, (ii) self-augmentation based methods, and (iii) spectral clustering based methods. The first group uses the AE to reconstruct the original input, which incorporates desired constraints on feature embeddings in the latent space. For instance, DEC [39] iteratively conducted the process of representation learning and clustering assignments via minimizing the Kullback-Leibler divergence. To preserve important data structure, IDEC [40] introduced AE to improve the clustering so that the local structure of data generating distribution can be maintained. The second group aims to encourage the consistency between original samples and their augmented samples by optimizing the networks. For example, IIC [41] sought to achieve the consistency of assignment probabilities by maximizing the mutual information of paired samples. The third group aims at constructing a robust affinity matrix for effective data partitioning. For instance, RCFE [42] utilized the idea of rank constraints and clusters data points in a low-dimensional subspace. Li et al. [43] utilized multiple features to construct affinity graphs for spectral clustering.

Benefiting from the breakthroughs of GNNs on graph-structured data, GNNs are capable of organically integrating node attributes and graph structures in a united way, and have emerged as a promising way for graph clustering. The basic idea is to group the nodes in the graph into several disjoint clusters. Similar to the deep clustering methods, a vast majority of existing graph clustering approaches [44, 45, 23, 24, 46, 47, 18, 22] also continue the paradigm of AE, in which the GAE and the variational GAE (VGAE) are leveraged to operate on graph-structured data. For example, to dynamically learn the importance of the neighboring nodes to the center node, DAEGC [45] employed the GAE to capture a compact representation by encoding the graph structures and node attributes. EGAE [23] learned the explainable representations based on the GAE that can be also used for various tasks. Compared with previous methods, our work further explores graph clustering by simultaneously preserving the relational similarity and reducing the redundancy of the learned representations based on both AE and GAE.

Recently, self-supervised learning (SSL) revitalizes and has achieved superior performance across numerous domains. This technique is completely free of the need for explicit labels [48], due to its powerful capability in learning effective representations from unlabeled data. The core procedure of SSL is first designing a domain-specific pretext task and training the networks on the pretext task, such that the learned representations can be more discriminative and applicable. Recently, many SSL approaches have been proposed to marry the power of SSL and deep learning [49, 50, 51, 52], and have shown competitive performance in various downstream application [53, 54, 55, 56, 57]. For example, SimCLR [49] employed multiple data augmentations and a learnable nonlinear transformation to train an encoder, such that the model can pull the feature representations from the same samples together. To alleviate the issue of the large batch size of SimCLR, MoCo [50] introduced a moving-averaged encoder to set up a dynamic dictionary for SSL. Furthermore, our proposed R²FGC inherits the advantages of SSL to preserve the consistent relation and reduce the redundant information among nodes from global and local views for graph clustering.

AE can reasonably explore the node attribute information, whereas the GAE can effectively capture the topological structure information. To gain a more comprehensive embedding and a better performance on downstream tasks, we consider both AE and GAE to reconstruct the input and learn fusional representation.

The AE module feeds the attribute information into the multi-layer perceptrons and extracts the latent representations by minimizing the reconstruction loss between the input raw data and the reconstructed data. The corresponding optimization objective is formalized as

where ${\mathbf{X}}\in\mathbb{R}^{n\times d}$ is the input attribute matrix and $\hat{{\mathbf{X}}}_{AE}\in\mathbb{R}^{n\times d}$ is the reconstructed data, $||\cdot||_{F}$ is the Frobenius norm, $\mathbf{Z}_{AE}\in\mathbb{R}^{n\times d^{\prime}}$ is the learned latent representation in AE, $\phi_{e}$ and $\phi_{d}$ are the encoder and decoder networks, respectively.

In the GAE module, following the improved version in [21], a multi-layer GCN is adopted to reconstruct the adjacency matrix and the attribute information. The corresponding reconstruction loss is formalized as

where $\alpha$ is a pre-defined hyper-parameter, $\mathbf{S}$ is the normalized adjacency matrix, $\hat{\mathbf{S}}$ is the reconstructed adjacency matrix produced by fusing respective inner products of the learned latent representation $\mathbf{Z}_{GAE}\in\mathbb{R}^{n\times d^{\prime}}$ resulting from the graph encoder and the attribute representations $\hat{{\mathbf{X}}}_{GAE}$ (i.e., the reconstructed weighted attribute matrix) resulting from the graph decoder, $\mathbf{W}_{e}^{(l)}$ and $\mathbf{W}_{d}^{(l)}$ are the layer-specific trainable weight matrices in the $l$-th graph encoder and decoder layers, respectively. The detailed fusion mechanism is discussed in the following Section IV-C, which unites the embedded representations from both AE and GAE to promote latent presentation learning in the graph augmentation fashion.

In this module, we learn the inherent relational information among the nodes based on augmentations on a given graph. One of the basic ideas is to preserve the similarity of the relational information from two augmented views, while the latent representation of the same node can vary after graph augmentation. Hence, we aim to increase the consistency of the relational information in each positive pair. It allows fine-grained mining of the node relationship. On the other hand, it is necessary to improve the discriminative capability of the resulting representations for graph clustering, thus we also decrease the correlation of the relational information in each negative pair. In the following, we first introduce the adopted graph augmentation strategies and relation extraction methods. Then, we describe the details of the subsequent relation preservation and relation de-redundancy.

Based on the given graph, we first construct two different graph views through augmentations, including

• •

  Attribute perturbation. For each value in the attribute matrix, we disturb it by multiplying a Gaussian random number with a small variance. This strategy performs a slight disturbance on the node features, which would not essentially change the semantic information.

• •

  Edge deletion. We remove some edges based on the node similarity obtained from the pre-learned latent embeddings. For each node, the edges that connect the nodes with low similarity are dropped in a certain proportion. Compared with random deletion, more semantic information can be preserved by referring to the node similarity.

• •

  Graph diffusion. We transform the adjacency matrix to a diffusion matrix by leveraging graph diffusion [58], which contributes to providing additional local information. Technically, given the transition matrix $\mathbf{T}$, the graph diffusion matrix $\mathbf{U}$ is formulated as

  $$\mathbf{U}=\sum_{j=0}^{\infty}\theta_{j}\mathbf{T}^{j},$$

  where $\theta_{j}$ is the weight coefficient. We adopt the personalized PageRank [59] to characterize graph diffusion, which is a special case. Specifically, $\mathbf{T}$ is chosen as the normalized adjacency matrix $\mathbf{S}$ and $\theta_{j}=\eta(1-\eta)^{j}$ with teleport probability $\eta\in(0,1)$. Then, the resulting diffusion matrix $\mathbf{U}$ has the form

  $$\mathbf{U}=\eta(\mathbf{I}-(1-\eta)\mathbf{S})^{-1}.$$

  (3)

After obtaining two augmented graph views ${\mathcal{G}}^{1}=\{{\mathbf{X}}^{1},\mathbf{S}^{1}\}$ and ${\mathcal{G}}^{2}=\{{\mathbf{X}}^{2},\mathbf{S}^{2}\}$, we perform AE and GAE on ${\mathbf{X}}^{1}$ and ${\mathbf{X}}^{2}$, which generates the attribute-level latent representations $\mathbf{Z}_{AE}^{1},\mathbf{Z}_{AE}^{2}$ and the structure-level latent representations $\mathbf{Z}_{GAE}^{1},\mathbf{Z}_{GAE}^{2}$. To meticulously characterize the relational information, we explore the similarities of each node to some anchor nodes from both global and local perspectives based on these representations.

Extraction of Global Anchors. For capturing the global relationship of a query node $v_{i}\in V$, the target is to sample diverse anchors from the whole graph nodes. Due to the neighborhood aggregation mechanism in GNNs, we argue that the high-degree nodes may receive more information when passing messages, while the low-degree nodes would receive less information. This may result in poor representations for the nodes with low degrees. Hence, we perform non-uniform sampling on the nodes to balance the qualities of the representations for low- and high-degree nodes. Specifically, we adopt an inverse degree-weighted distribution for sampling anchors, which puts a larger sampling probability on a lower-degree node. The sampling weight and probability for each node, respectively, are as follows,

where $\beta\in(0,1)$ is a hyper-parameter to control the skewness of the distribution, and $\tilde{d}_{i}$ is the degree of node $v_{i}$. Moreover, quasi-Monte Carlo (QMC) sampling methods usually can achieve a higher convergence rate than Monte Carlo (MC) methods [60]. Hence, based on the defined discrete distribution, we perform multinomial sampling in the QMC fashion [61, 62]. Instead of the uniform random number (the MC fashion), we leverage the randomized one-dimensional low-discrepancy point set $\{(2i-1)/(2M_{1})+\omega\mod 1\in[0,1]:\omega\sim U(0,1),i=1,\ldots,M_{1}\}$ to do multinomial sampling on the discrete distribution in each training epoch. Randomization is used to avoid the same sample in different epochs and increase the randomness for extracting more diverse anchors. For each node $v_{i}\in V$, we denote the index set of the sampled anchors from the global view as $A_{i}^{g}$ and $|A_{i}^{g}|=M_{1}$.

Extraction of Local Anchors. To fully explore the relational information, besides the global anchor sampling, we also concentrate on the local relational information. Graph diffusion removes the restriction of using only the direct neighbors and alleviates the problem of noisy and often arbitrarily defined edges. It leads that the diffusion matrix $\mathbf{U}$ in (3) can acquire richer structural information in the local view compared with traditional GNNs. Hence, we leverage graph diffusion to generate the local anchors according to the scores in $\mathbf{U}$. Specifically, the values in the $i$-th row of $\mathbf{U}$ can reflect the influence between node $v_{i}$ and all the other nodes. We select the nodes with the $M_{2}$ largest scores in the $i$-th row of $\mathbf{U}$ as the local anchors of node $v_{i}$. It makes that the local anchors of $v_{i}$ share similar semantic information to $v_{i}$, which allows us to extract more effective local relations. For each node $v_{i}\in V$, we denote the index set of the local anchors as $A_{i}^{l}$ and $|A_{i}^{l}|=M_{2}$.

Based on these global- and local-view anchor sets $A_{i}^{g},A_{i}^{l},i=1,\ldots,n$, we extract the relational information of the nodes in the sense of similarity. We use the AE latent representations $\mathbf{Z}_{AE}^{1}=(\mathbf{z}^{1}_{AE,1},\ldots,\mathbf{z}^{1}_{AE,n})^{\top},\mathbf{Z}_{AE}^{2}=(\mathbf{z}^{2}_{AE,1},\ldots,\mathbf{z}^{2}_{AE,n})^{\top}$ to illustrate the detailed process. Specifically, given a query node $v_{i}\in V$, we calculate the similarities between the embedded representation of $v_{i}$ in $\mathbf{Z}_{AE}^{1}$ and the embeddings of these anchors in $\mathbf{Z}_{AE}^{2}$ by

Similarly, we also calculate the similarities between the embedding of $v_{i}$ in $\mathbf{Z}_{AE}^{2}$ and those of the anchors in $\mathbf{Z}_{AE}^{2}$ by

Hereafter, let $\mathbf{r}^{u}_{c}(i)$ be the relation vector composed by $r^{u}_{c}(i,k)$ with $k$ traversing the whole index set $A_{i}^{c}$ of node $v_{i},i\in\{1,\ldots,n\}$, and $\mathbf{R}^{u}_{c}=(\mathbf{r}^{u}_{c}(1),\ldots,\mathbf{r}^{u}_{c}(n))^{\top}$ be the relation matrix for any $u\in\{1,2\},c\in\{g,l\}$.

Relation Preservation. To make the relational information invariant to augmentation, we maximize the proximity of $\mathbf{r}^{1}_{c}(i)$ and $\mathbf{r}^{2}_{c}(i)$ from both global and local views, i.e., we maximize the attribute-level relational similarities of all the positive pairs under augmentation, which are formulated by

and

We can similarly obtain the structure-level relational similarities $R_{GAE}^{g}$ and $R_{GAE}^{l}$ corresponding to GAE from both views. This operation helps to learn representations that are more reflective of the relationships between the attribute and topological information of all the nodes.

Relation De-redundancy. In addition, besides preserving the relational similarity under augmentations, the discriminative capability of the latent representation is also important for the downstream graph clustering task. Hence, we decrease the correlations of the relation vectors for different nodes from both global and local views. It contributes to filtering redundant information and improving the separating capability for better clustering performance. Specifically, we minimize the attribute-level relational correlations of all the negative pairs, which are formulated as follows,

and

In like manner, we can obtain the corresponding structure-level loss under GAE from global and local views, denoted by $C_{GAE}^{g}$ and $C_{GAE}^{l}$, respectively.

Based on the above discussion, we can capture the augmentation-invariant relational information and conduct redundancy-free relational learning by minimizing the total relation loss $L_{RE}=L_{REA}+L_{REG}$ with

The loss $L_{RE}$ takes into account both efficient representation learning and reduction of redundant information upon the relation extraction of the nodes, which allows for better guidance of downstream tasks.

In this section, to obtain fine-grained representations of the nodes, we discuss the fusion mechanism of the attribute- and structure-level latent representations based on augmentations. First, we take a weighted summation of the four parts to fuse the embedded representations from the two levels as follows,

where $\mathbf{W}_{1},\mathbf{W}_{2}\in\mathbb{R}^{n\times d^{\prime}}$ are trainable weight matrices to control the importance of the two types of representations and $\odot$ is the Hadamard product. Based on $\tilde{\mathbf{Z}}_{c}$, we further blend the embeddings from both global and local views to refine the fused information. From the local view, we adopt the neighborhood aggregation operation on $\tilde{\mathbf{Z}}_{c}$ to enhance the local information, whereas, from the global view, we utilize the self-correlation matrix of the nodes characterized by $\tilde{\mathbf{Z}}_{c}$ to improve the exploitation of the global information, which is normalized by the softmax function. Specifically, the final formula of the fused representation is

where $\delta$ is a trainable weight parameter. With $\tilde{\mathbf{Z}}$, we can obtain the reconstructed attribute matrix $\hat{{\mathbf{X}}}_{AE}$ in (1) and weighted attribute matrix $\hat{{\mathbf{X}}}_{GAE}$ in (2) by feeding $\tilde{\mathbf{Z}}$ into the decoders of AE and GAE, respectively. The reconstructed adjacency matrix is calculated by fusing the self-correlations of the learned representations in GAE, which is formulated as

The above fusion process is similar to [21].

In addition, under the neighbor aggregation mechanism, GCN updates node representations by aggregating information from the neighbors. However, when stacking multiple layers, the learned representations would become indistinguishable, seriously degrading the performance, which is the so-called over-smoothing issue [63, 64]. Hence, it is important to balance the message aggregation ability and over-smoothing issue. To alleviate the problem in GAE, we incorporate a novel propagation-regularization loss to enhance information capturing while alleviating over-smoothing defined as

where ${\mathcal{E}}$ contains the embedding matrix in each layer of both the encoder and decoder in GAE and $\nu(\cdot)$ is the metric function, such as the cross entropy, Kullback-Leibler (KL) divergence, and the Jensen-Shannon divergence. Propagation regularization simulates a deep GCN by supervision at a low cost, which enables current embeddings to capture further information contained in the deeper layer. Compared with directly increasing the GCN layers, we can more finely balance the information capture ability and the over-smoothing problem by adjusting the weight of the loss.

Thereby, the total reconstruction loss is computed by

where $\epsilon$ is the pre-defined hyper-parameter to adjust the influence ratio, and the reconstruction losses $L_{AE}$ and $L_{GAE}$ in AE and GAE are defined in (1) and (2), respectively.

Graph clustering is essentially an unsupervised task with no feedback available as reliable guidance. To this end, we perform a clustering layer on the fused representation $\tilde{\mathbf{Z}}$ in (5) and use the soft labels derived by a probability distribution as a self-supervised signal to jointly optimize the redundancy-free relational learning framework for graph clustering.

First, by using the student’s $t$-distribution as a kernel, we calculate the soft cluster assignment probabilities $\mathbf{Q}_{1}=(q_{1,ij}),\mathbf{Q}_{2}=(q_{2,ij}),\mathbf{Q}_{3}=(q_{3,ij})\in\mathbb{R}^{n\times K}$ upon the latent embeddings $\tilde{\mathbf{Z}},(\mathbf{Z}_{AE}^{1}+\mathbf{Z}_{AE}^{2})/2,(\mathbf{Z}_{GAE}^{1}+\mathbf{Z}_{GAE}^{2})/2$, respectively, to measure the similarities between the latent representations and cluster centroids, i.e., each value indicates the probability of assigning the $i$th node to the $j$th cluster. For example, $q_{1,ij}$ is computed as follows,

where $\tilde{\mathbf{Z}}=(\tilde{\mathbf{z}}_{1}^{\top},\ldots,\tilde{\mathbf{z}}_{n}^{\top})^{\top}$ and $\boldsymbol{\mu}_{j}$’s are the cluster centroids. The $q_{2,ij}$ and $q_{3,ij}$ can be calculated similarly. The $\boldsymbol{\mu}_{j}$’s are initialized by performing $k$-Means on the pre-trained fused representation. When the network is well trained, we adopt the fusion-based assignment matrix $\mathbf{Q}_{1}$ to measure the cluster assignment probability of all the nodes, i.e.,

where $y_{i}$ is the predicted cluster of node $v_{i}$ for $i=1,\ldots,n$.

Next, we introduce an auxiliary confident probability distribution $\mathbf{P}=(p_{ij})\in\mathbb{R}^{n\times K}$ to improve the confidence of the soft assignment, which is derived from $\mathbf{Q}_{1}$ and formulated as

To make the data representation close to cluster centroids and improve cluster cohesion, we minimize the KL divergence loss between $\mathbf{P}$ and $\mathbf{Q}_{1},\mathbf{Q}_{2},\mathbf{Q}_{3}$ as follows,

By utilizing the confident distribution $\mathbf{P}$, the process self-supervises the cluster assignment without any label guidance. We integrate the latent representations from AE, GAE, and the fusion mechanism in the self-supervised clustering procedure to obtain more accurate clustering results.

To sum up, the total loss $L$ in the whole framework of R²FGC is composed of the relation loss, the reconstruction loss, and the self-supervised clustering loss, i.e.,

where $\kappa$ is a pre-defined hyper-parameter to balance the weight of the clustering loss. The training process of our proposed R²FGC is summarized in Algorithm 1.

For the scalability of large-scale datasets, we adopt the mini-batch stochastic gradient descent to optimize our method. Assume that the batch size is $B$ and the dimensions of each layer of AE and GAE are $\bar{d}_{1},\ldots,\bar{d}_{L_{1}}$ and $\tilde{d}_{1},\ldots,\tilde{d}_{L_{2}}$, respectively. Given a graph with $n$ nodes and $|E|$ edges, the dimension of the original attributes is $d$. The time complexities of AE and GAE are $O(n\sum_{i=1}^{L_{1}}\bar{d}_{i}\bar{d}_{i-1})$ and $O(|E|\sum_{i=1}^{L_{2}}\tilde{d}_{i}\tilde{d}_{i-1})$ with $\bar{d}_{0}=\tilde{d}_{0}=d$, respectively. For each batch, the complexity of the relation learning module is $O(B(B+d^{\prime})(M_{1}+M_{2}))$ based on $d^{\prime}$-dimensional latent representations. Moreover, we perform the representation fusion and propagation regularization in $O(B^{2}d^{\prime}+B\log B)$ time and conduct the self-supervised clustering in $O(BK+B\log B)$ time with $K$ classes in the task. Hence, the total computational complexity of our method R²FGC is $O(n\sum_{i=1}^{L_{1}}\bar{d}_{i}\bar{d}_{i-1}+|E|\sum_{i=1}^{L_{2}}\tilde{d}_{i}\tilde{d}_{i-1}+n(B+d^{\prime})(M_{1}+M_{2})+n(Bd^{\prime}+K))$, which is linearly related to the numbers of nodes and edges.

Datasets. For comparison, we perform the proposed method R²FGC on five commonly used benchmark datasets. Four of them are graph datasets, including a paper network ACM¹¹1http://dl.acm.org/, a shopping network AMAP²²2https://github.com/shchur/gnn- benchmark/raw/master/data/npz/
amazon_electronics photo.npz, a citation network CITE³³3http://citeseerx.ist.psu.edu/index, and an author network DBLP⁴⁴4https://dblp.uni-trier.de; another is a non-graph dataset, i.e., a record dataset HHAR[65]. Following [18], for the non-graph data, the adjacency matrix is generated by the undirected $k$-nearest neighbor graph. Table I briefly summarizes the information of these benchmark datasets.

Compared Methods. To illustrate the superiority of our proposed R²FGC, we compare its clustering performance with some state-of-the-art clustering methods, which are divided into four categories, i.e., the classical shallow clustering method $k$-means, the AE-based methods, the GCN-based methods, and the combination of AE and GCN. The AE-based methods contains AE[27], DEC[39], and IDEC[40]. They convert the raw data to low-dimensional codes to learn feature representations by AE and then perform clustering over the learned latent embeddings. The GCN-based methods include GAE, VGAE[28], DAEGC[45], and ARGA[46]. They adopt the GCN encoder to learn the node content and topological information for clustering. In addition, some methods combine AE and GCN to boost the embedded representations for clustering, which contains SDCN [18], DFCN[21] and AGCC [24]. These methods integrate GCN with AE from different perspectives to jointly train the clustering network.

Training Procedure. The training of our method R²FGC includes two phases. First, following [21], the AE and GAE are pre-trained independently for 30 epochs to minimize their respective reconstruction loss functions. Both sub-networks are integrated into a united framework for another 100 epochs to obtain the initial representations and cluster centroids. Then, we train the whole network for at least 300 epochs until convergence to minimize the total loss in (9). Following the compared methods, to alleviate the adverse influence of the randomness, we repeat the experiment 10 times to evaluate our method and report the mean values and the standard deviations (i.e., mean±std) of the considered metric values. We implement our method using PyTorch 1.8.0 and Pytorch Geometric 1.7.2, which can easily train GNNs for a variety of applications associated with graph-structured data.

Parameter Settings. For a fair comparison, we adopt the same parameter setting for AE and GAE as [21], i.e., the layers of the encoder (/decoder) for AE and GAE are set to 4 and 3, respectively; the dimensions of the encoder (/decoder) for AE are set to 128, 256, 512, 20 in turn; the dimensions of the encoder (/decoder) for GAE are set to 128, 256, 20 in turn. The network is trained with the Adam optimizer. The learning rate is set to 5e-5 for ACM, 1e-4 for DBLP, and 1e-3 for AMAP, CITE, and HHAR. The hyper-parameters $M_{1}$ and $M_{2}$ are set to $\{$256, 8$\}$. Moreover, the parameters $\alpha,\eta,\beta,\epsilon,\kappa$ are set to 0.1, 0.2, 0.8, 5e3, 10, respectively. The optimization stops when the validation loss comes to a plateau.

Evaluation Metrics. To evaluate the clustering performance of each compared method, we adopt four widely used evaluation metrics following [18], i.e., Accuracy (ACC), Normalized Mutual Information (NMI), Average Rand Index (ARI), and Macro F1-score (F1). For each metric, a larger value implies a better clustering result.

The experimental results of our method and eleven compared methods on five benchmark datasets are reported in Table II, in which the bold and underlined values indicate the best results in all the methods and all the baselines, respectively. From these results, we have the following observations.

• •

  Compared with shallow clustering method $k$-means, these deep graph clustering methods clearly show preferable performance. It indicates that the strong capability for learning representation of deep neural network methods enables exploit more meaningful information from graph-structured data for clustering.

• •

  The purely AE-based methods (AE, DEC, and IDEC) perform worse than the methods combining AE and GCN (SDCN, DFCN, and AGCC) in most cases. The reason may be that the AE-based methods only leverage the attribute information to learn the latent representation, which overlooks the structure-level semantic information. Similarly, the purely GCN-based methods (GAE, VGAE, DAEGC, and ARGA) also show inferior performance than SDCN, DFCN, and AGCC in most circumstances. It indicates that integrating AE into GCN can capture the attribute and structure information more effectively from complementary views.

• •

  Our method R²FGC achieves the best clustering performance compared with all the baselines in terms of the four considered metrics over all the datasets. For both graph and non-graph data, our approach represents a significant improvement over the baselines. For example, compared with the best results among all the baselines, for the ACM dataset, our method relatively improves 1.68%, 4.35%, 5.10%, 1.82% on ACC, NMI, ARI, F1; for the AMAP dataset, our method improves 5.72%, 6.75%, 11.55%, 5.18% on ACC, NMI, ARI, F1; for the DBLP dataset, our method improves 6.51%, 16.29%, 19.87%, 6.39% on ACC, NMI, ARI, F1, respectively.

• •

  The reasons for the superiority of our method R²FGC are that a) R²FGC extracts the inherent relational information based on AE and GAE from both local and global views under augmentation, which allows for better exploration of both attribute and structure information; b) Under augmentation, R²FGC preserves the consistent relationship among the nodes but not the latent representations, which expects to learn more essential representations of the semantic information; c) R²FGC decreases the redundant relation among the nodes for learning discriminative and meaningful representations, which can better serve the graph clustering; d) R²FGC couples AE and GAE together in the representation fusion mechanism to fully integrate and refine the attribute and structure information; e) R²FGC also brings the propagation regularization to mitigate the possible over-smoothing problem caused by GAE to promote the clustering performance. With the addition of relation extraction, relation preservation and de-redundancy strategies, R²FGC outperforms all the baselines upon the fusion mechanism of AE and GAE and the regularization method of alleviating over-smoothing.

In this section, to further investigate the validity of our proposed method, we conduct some ablation experiments to study the contribution of each component of R²FGC. We mainly focus on the influence of global-view relation extraction (gloRE), local-view relation extraction (locRE), relation preservation (REpre), relation de-redundancy(REder), and propagation regularization (PR). In addition, we make some discussion on the proposed global sampling strategy.

Effects of gloRE and locRE. In the relation extraction module, we explore the inherent relation from both global and local views. The former view learns the global relation of the nodes and the latter concerns the neighbor relation. We perform some ablation experiments to verify the respective effectiveness of the global- and local-view strategies. Specifically, we consider the following two cases:

• •

  R²FGC w/o gloRE: R²FGC without considering the global-view relation extraction;

• •

  R²FGC w/o locRE: R²FGC without considering the local-view relation extraction;

The corresponding results are displayed in Table III. From the comparison of R²FGC w/o gloRE and R²FGC w/o locRE, for the ACM dataset, local-view relation extraction has a greater effect than the global-view one on clustering in terms of ACC, NMI, ARI, and F1, while for the CITE and DBLP datasets, the global-view relation extraction may have a more prominent contribution. As for the AMAP and HHAR datasets, R²FGC w/o gloRE and R²FGC w/o locRE show close metric values, which indicates that global- and local-view extractions almost play equal roles. Moreover, R²FGC consistently shows better performance than R²FGC w/o gloRE and R²FGC w/o locRE over the five considered datasets. Hence, these results illustrate that both views are necessary and important for achieving good clustering performance.

Effects of gloRE, locRE, and PR. Additionally, relation preservation is used to learn the effective representations by preserving the consistent relation information, whereas the relation de-redundancy conduces to reduce the confusing information, which benefits obtaining discriminative embeddings. Moreover, we adopt propagation regularization to relieve the over-smoothing issue. Hence, we also explore their respective efficiencies in the ablation experiments, i.e., four cases are considered as follows:

• •

  R²FGC w/o REpre: R²FGC without considering the relation preservation;

• •

  R²FGC w/o REder: R²FGC without considering the relation de-redundancy;

• •

  R²FGC w/o REpre & REder: R²FGC without both relation preservation and de-redundancy;

• •

  R²FGC w/o PR: R²FGC without adopting the propagation-regularization trick.

The corresponding results are also shown in Table III. Comparing R²FGC w/o REpre with R²FGC w/o REder, it is observed that relation preservation outperforms relation de-redundancy for the ACM dataset; relation de-redundancy shows more significant power to improve the clustering performance for the AMAP, CITE, and DBLP datasets; these two strategies have almost equal impact on the HHAR dataset. Moreover, by contrasting with R²FGC w/o REpre & REder, both R²FGC w/o REpre and R²FGC w/o REder give better clustering results with higher metric values, which implies that both relation preservation and relation de-redundancy possess the capability to promote the effect of graph clustering. In addition, by comparing R²FGC w/o PR and R²FGC w/o REpre & REder, for the ACM, AMAP, and HHAR datasets, the over-smoothing issue has a more significant impact on clustering performance, whereas, for the CITE and DBLP datasets, the relation extraction is more important for good performance. For example, R²FGC on the ACM dataset has 1.99% relative improvement over R²FGC w/o PR in terms of NMI; R²FGC on the CITE dataset obtains 6.28% improvement over R²FGC w/o REpre & REder in terms of ARI. Hence, these results demonstrate that all of the proposed components in R²FGC are efficient for reaching informative representation and good performance for graph clustering.

Discussion on Global Sampling Strategy. To further illustrate the effectiveness of the QMC inverse degree-weighted distribution sampling for extracting global anchors, we perform experiments to compare it with two MC cases on the AMAP, DBLP, and HHAR datasets, i.e., we consider the following three cases:

• •

  R²FGC with QMC global sampling (Ours): R²FGC with considering QMC inverse degree-weighted distribution sampling, i.e., the low-discrepancy point set is used in the multinomial sampling;

• •

  R²FGC with MC global sampling: R²FGC with considering MC inverse degree-weighted distribution sampling, i.e., the uniform random numbers are used;

• •

  R²FGC with SRS: R²FGC with considering simple random sampling for drawing global anchors.

The results are depicted in Figure 2. Comparing the three strategies, R²FGC with QMC global sampling shows better performance over the three considered datasets in terms of the average ACC, NMI, ARI, and F1 scores. Moreover, R²FGC with MC global sampling outperforms R²FGC with SRS, which implies that inverse degree-weighted distribution sampling is indeed effective to avoid poor representations. In addition, from the error bars in Figure 2, we can also find that R²FGC with QMC global sampling leads to smaller variances for the metric values, which benefits from the high convergence rate of the QMC sampling strategy. The sampled global anchor set is a better representation of the target distribution, which motivates the subsequent representation learning to have a better and more stable performance. In this way, our proposed sampling method guarantees good robustness to relation extraction and thus to clustering performance.

In this section, we examine the sensitivity of the proposed R²FGC to the hyper-parameters. For the global- and local-view relation extraction in Section IV-B, we need to pre-define the numbers of the global and local anchors $M_{1}$ and $M_{2}$ for sampling. Hence, we investigate the effect of varying $M_{1}$ and $M_{2}$ on ACM, AMAP, CITE, and HHAR datasets. For each dataset, we consider $M_{1}=\{128,256,512,1024\}$ and $M_{2}=\{4,8,16,32\}$. When $M_{1}$ is varied, we fix $M_{2}$ to its optimal setting as in Section V-A, and vice versa. Additionally, we explore the impact of two loss weight parameters $\epsilon$ and $\kappa$ on ACM, AMAP, CITE, and DBLP datasets. We vary $\epsilon$ across $\{5{\rm e}2,1{\rm e}3,5{\rm e}3,1{\rm e}4\}$ and $\kappa$ across $\{1,5,10,50\}$. The results are depicted in Figures 3 and 4, respectively.

Performance of Different Amounts of Global Anchors. From Figure 3, it can be seen that the average accuracies for the considered datasets are relatively stable as $M_{1}$ changes. It may be due to that with the QMC multinomial sampling, the drawn anchors can well mimic the defined inverse degree-weighted distribution even if $M_{1}$ is small. It helps to solve the problem caused by varying qualities of the learned representations for the nodes with different degrees. On the other hand, we draw different samples in different training epochs based on the randomization strategy, which increases the diversity of the samples to catch a broad relationship, even with a small number of global anchors. Therefore, the clustering performance is robust to the number of global anchors based on the proposed sampling strategy.

Performance of Different Amounts of Local Anchors. As for $M_{2}$, it can be found that on the four datasets, as $M_{2}$ increases, it promotes the clustering performance first and then shows a weakening tendency. The possible reason may be that small $M_{2}$ cannot well collect the neighboring information, whereas large $M_{2}$ may absorb nodes involved in other clusters, which can disturb the extraction of local relation. Hence, a moderate number of local anchors is preferable and a well-designed deterministic sampling is desirable to avoid the intake of inconsistent information from other nodes.

Performance of Different Amounts of Loss Weights. As shown in Figure 4, when $\kappa$ is small, increasing $\epsilon$ leads to a decrease in model performance. This is because large $\epsilon$ enhances the information aggregation ability of the nodes, which is equivalent to a deep GCN and thus increases the risk of over-smoothing, while small $\kappa$ means a low self-supervision ability, which results in poor cohesion and insufficient discrimination in node representations. As the increase of $\kappa$, better representation cohesion achieves, and increasing $\epsilon$ appropriately is promising to improve the performance by balancing the strength of neighbor aggregation in GCN and the weakness of over-smoothness. However, when $\epsilon$ becomes excessively large, there may be a slight decline in performance due to the over-smoothing issue on some datasets. In addition, when $\epsilon$ is fixed, increasing $\kappa$ results in an increasing trend in model performance on ACM and AMAP datasets. However, on CITE and DBLP datasets, excessively large $\kappa$ leads to a decreasing trend. One possible reason is that CITE and DBLP represent citation networks and author networks, respectively, where different articles and individuals may belong to distinct disciplines or communities. Forcing strong cohesion in these cases may lead to suboptimal results. Overall, we recommend to set $\kappa$ around 10 and $\epsilon$ around 5e3 for satisfying performance. When dealing with a new dataset, a small-scale hyper-parameter tuning around the recommended values is needed due to the dataset’s specific characteristics.

In this section, we analyze the convergence of our proposed method R²FGC, the curves of the training losses are shown in the Figure 5. It can be observed that our method demonstrates graceful convergence across different datasets AMAP and HHAR. The reason behind this can be attributed to our pre-training learning based on AE and GAE, which provides us with a well-initialized representation. As a result, the initial loss optimization has the correct gradient direction, leading to a rapid decrease in loss. Additionally, our method effectively maintains the relational similarity between nodes in the graph while reducing the redundancy of learned representations. This allows the learned representations to possess highly rich semantic information and strong discriminative capabilities. It enables similar nodes closer to each other while better distinguishing unrelated nodes, facilitating the formation of clusters. This also motivates the training objective to converge to lower value, leading to better clustering performance.

To verify the superiority of the proposed propagation-regularization loss in alleviating over-smoothing issue, we compare the effects of different GCN layers in GAE encoder and different values of $\epsilon$ by mean average distance (MAD) and clustering performance (i.e., accuracy). MAD reflects the smoothness of node representations by calculating the mean of the average cosine distance between the nodes and other nodes [64]. A smaller MAD indicates a higher global smoothness. The analysis results are shown in Figure 6.

It can be observed that as the number of GCN layers in GAE encoder increases, indicated by the dashed line in the figure, both MAD and accuracy exhibit a decreasing trend. It implies that larger GCN layers cause nodes to immensely absorb information from farther neighbors and thus can lead to indistinguishable node representations, exacerbating the over-smoothing issue and resulting in performance degradation. On the other hand, our proposed propagation-regularization loss shows a slight decrease in MAD and a gradual increase in clustering performance as $\epsilon$ increases to a certain value (e.g., 2e3 for AMAP, 1e4 for DBLP). This suggests that our propagation-regularization loss is equivalent to simulating a GCN of a fractional layer, which possesses the capability to ease the increase of smoothness and meanwhile enhance the expressive power of node representations, thereby promoting the clustering performance. However, when $\epsilon$ is particularly large, both MAD and accuracy decrease sharply. This is because excessively large $\epsilon$ amplifies the risk of over-smoothness. Therefore, selecting an appropriate weight is crucial in balancing node expressiveness and the over-smoothing issue.

To visually verify the validity of our proposed R²FGC, we plot 2D $t$-distributed stochastic neighbor embedding ($t$-SNE) visualizations[66] for the learned representations on the ACM, CITE, DBLP, and HHAR datasets. We compare the $t$-SNE visualizations of the embeddings resulting from R²FGC with those from the raw data and DFCN (the best method among the baselines in Section V-B) to enable a visual comparison. The plots are shown in Figure 7. The results of $t$-SNE on the four raw data clearly have poor separability for different clusters. Compared with the raw data, more distinguishing visualizations in R²FGC and DFCN demonstrate that deep graph clustering methods indeed make great performance improvements. Comparing R²FGC with DFCN, the latent representations obtained by our method R²FGC show better separability for different clusters, where the samples from the same cluster have better aggregation and those from different clusters have a bigger gap. Such a phenomenon illustrates that our proposed method learns more discriminative representations and produces more effective cluster assignments compared with state-of-the-art methods.