Graph Clustering with Masked AutoEncoders

Q1.

For large-scale datasets, our experimental results on ogbn-arxiv have demonstrated our advantage as a non-parametric method, capable of predicting the number of clusters in large datasets. However, the disadvantage is that, as the data scale increases, hindered by noise interference and dimensionality growth, GCMA, like most methods, experiences a gradual decline in performance. Due to space limitations, we believe it is unnecessary to elaborate excessively on this universally acknowledged aspect in the main text. However, we will provide corresponding experimental results below as supporting evidence. We ran our model on the larger dataset Reddit. While other baseline such as EGAE will have out of memory problem. There is only one way to get the result for the parameter class method S3GC[4].SHOT represents the accuracy of the predicted k-value.

Q2.

Additional result analyses have been incorporated into the original text. In Section 4.4, our intention was to demonstrate the superiority of the GCMA method and the impact of integrating AE encoding, namely the GCMA-A model. Therefore, visual results for only two datasets are presented along with brief explanations. From another perspective, Section 4.4 serves as a visual representation of Table 3. It can be observed from the graphs that the separation effect between clusters is worse for GCMA-A, proving the effectiveness of integrating AE encoding. The integrated graph embedding makes full use of node information to correct the clustering results.

Q3.

We did not have the methodology of the literature [1] when we started writing this paper, so we added additional experiments. The experimental dataset is cite. However, it is clear that this is a parametric class method that requires the correct number of clusters k to be entered in advance for optimal performance.

Q4.

The self-optimization method we applied indeed stems from deep clustering research, as seen in references [2] and [3]. This method has become nearly a universal approach within the clustering domain for enhancing the quality of autoencoder encodings. It achieves this by compelling better representations through self-supervised training. Subsequent ablation experiments substantiate this point, and for this aspect, we conducted more in-depth experimental research, specifically investigating the impact of the number q on the performance of the self-supervised module (refer to Table 4). The results of these experiments consistently indicate that our application of the optimal number q for the self-supervised optimization module yields the best performance.

[1] Yi et al., Redundancy-Free Self-Supervised Relational Learning for Graph Clustering

[2] Hong Yuan，et al.. Embedding graph auto-encoder for graph clustering

[3]Chun Wang, et al.Attributed graph clustering: A deep attentional embedding approach.

[4]Fnu Devvrit, et al.S3GC: Scalable Self-Supervised Graph Clustering

Dear reviewer, I have submitted my reply a few days ago. Now the deadline for public comment is approaching, but I observe that you have not replied to my comment. I would be happy if you let me know if you still have some questions or replies. If so, I will reply promptly. Looking forward to your reply.

Thank you for your appreciation of our work. In response to your questions, we provide detailed explanations below.

W1.

Certainly, as the reviewer pointed out, graph masking methods have become increasingly prevalent. However, there hasn't been a well-performing non-parametric method for graph clustering. In earlier works like MGAE, edge masking was applied to the graph, followed by decoding through cross-correlation. Subsequent methods such as MaskGAE utilized single-edge masking and path masking. More recent approaches like GiGaMAE and GraphMAE introduced feature masking and re-masking to enhance training data for better results. However, current research predominantly focuses on the study of graph masking encoding performance, with downstream tasks mainly oriented towards link prediction and node classification. There is a lack of a dedicated deep learning model applied to clustering tasks. The only existing small-scale downstream experiment on deep clustering with graph masking is found in GiGaMAE, but this model did not incorporate specific improvements for clustering, resulting in relatively poor experimental performance. In light of these research developments, GCMA innovatively combines graph masking technology with clustering. We seamlessly integrate graph masking technology, utilizing single-edge, node, and re-masking, and incorporating AE encoding. We introduce a multi-objective decoder specifically tailored for clustering tasks. In terms of graph encoding technology, our differentiator lies in the modifications made specifically for clustering tasks. We inherit multi-objective reconstruction and the second CFSFDP decoder, achieving better clustering performance while keeping training costs low.

W2.

Next, we provide a detailed explanation of the process for predicting the clustering number, k. In the main text, especially in Figure 2, we have depicted the relevant flowchart. The algorithm operates based on two fundamental assumptions. First, data points near the cluster center have lower density, and second, data points are farther away from other centers with higher density. Sample point density is defined as $\rho$, and the minimum distance between a data point and points with higher density is defined as $\delta$. Among all data points, there are points with a product $\gamma_i$ that is larger, representing points with higher density $\rho$. These points are the centers of clusters. After determining several centers, the remaining data points are assigned in order of density, belonging to the point with higher density closest to them. This way, we can automatically obtain the clustering number, k. We integrate this process into our end-to-end GCMA model, optimizing the distance between sample points and cluster centers, further enhancing the algorithm's performance.

W3.

Regarding the consideration for dataset selection, our primary concern is the distinction between graph and non-graph data. This allows for better validation of our model's generalization capability. For graph data, most clustering algorithms primarily utilize referenced graph datasets, such as in the literature SDFN, DFCN, S3GC. Rarely do we see other types of graph data in related research.

Q1.

For other baselines in Table 3, we provided the correct k value as input. Otherwise, it would be unfair to compare with other parameter-based methods. As mentioned in our Figure 1, the overall clustering performance of parameter-based methods would significantly decline.

Q2.

We did not find a non-parametric method that is highly suitable for graph data. Therefore, we had to use non-parametric methods from Table 2 as baselines for performance comparison. However, we acknowledge that this might be unfair to methods not specifically designed for graph data, as they may struggle to showcase their performance on non-specialized data. Here are the additional experimental results we have supplemented. We choose the Cora dataset.

Q3.

As mentioned in our response in section "W2," the algorithmic process of CFSFDP allows us to obtain points with larger $\gamma_i$ values, which we consider as cluster centers, thus determining the number of clusters, k. It is essential to highlight the improvements we introduced in our work. First, in our enhancements, we employed a Gaussian kernel to determine the truncation distance. Second, the original CFSFDP, being an independent algorithm, was integrated into the end-to-end GCMA, where we designed a unified loss function for optimization. These improvements position CFSFDP as the second decoding module within GCMA.

Finally, thank you again for taking the time to review my paper and I look forward to hearing from you again.

Dear reviewer, I have submitted my reply a few days ago. Now the deadline for public comment is approaching, but I observe that you have not replied to my comment. I would be happy if you let me know if you still have some questions or replies. If so, I will reply promptly. Looking forward to your reply.

Thank you for your appreciation of our work. In response to your questions, we provide detailed explanations below.

Firstly, we want to clarify the distinctions between our approach and GraphMAE. GraphMAE primarily masks nodes and their corresponding row vectors, replacing the decoder with a GNN layer (GAT/GIN) instead of an MLP. In contrast, our method masks weights, including nodes and edges, and employs a multi-objective decoding approach to address decoding challenges.

Regarding the previously proposed CFSFDP method, it had three main issues. Firstly, the algorithm's truncation distance, dc, originally required human experience for determination. In our enhancement, we utilize a Gaussian kernel, enabling automatic determination of the truncation distance. Secondly, the original algorithm necessitated the semi-automatic input of the cluster number, k, based on observed built-in parameters. We, however, directly obtain cluster centers by calculating parameters γi and point density. Lastly, the original CFSFDP operated as an independent algorithm, but we integrated it into the end-to-end GCMA, designing a unified optimized loss function. These improvements position CFSFDP as the second decoding module in GCMA. Consequently, our method operates as a non-parametric approach, eliminating the need for pre-inputting the cluster number k. The original method fails to achieve comparable experimental results, and notably, few researchers in the field of graph clustering have employed this method.

Additionally, concerning your remark about not conducting comparative experiments between SSL and the proposed method, this decision stems from the fact that, as a deep clustering model, the SSL module has become a standard component, as seen in AGC and EGAE within our model. Its coercive learning approach has been validated to optimize embeddings to some extent. Therefore, our comparative experiments focused solely on parameter selection within SSL, as detailed in Table 4.

Finally, we would like to explain our motivation for choosing baselines. Our experiments aim to investigate the clustering performance and the accuracy of predicting k for GCMA. The logical design of our experiments is as follows. Two performance metrics are considered: 1) the accuracy of predicting clustering numbers, k, and 2) graph clustering performance. For the former, our experimental baseline is a non-parametric clustering method capable of predicting k. As there are few methods specifically designed for graph clustering, we introduce some deep clustering methods with SOTA performance as benchmarks. For the latter, we need to compare graph clustering performance, thus referencing baseline methods 1, 2, and 3, which are recent SOTA methods. We believe applying graph data to new experimental results obtained through clustering methods would be unfair. The selected graph clustering methods are also among the most effective in recent years, as indicated by various references, including the latest literature [1], which cites these baselines. Experimental results demonstrate that we still achieve considerable performance in graph clustering.

Once again, we appreciate your time in reviewing our paper and look forward to your further feedback.

[1] Yi et al., Redundancy-Free Self-Supervised Relational Learning for Graph Clustering

Dear reviewer, I have submitted my reply a few days ago. Now the deadline for public comment is approaching, but I observe that you have not replied to my comment. I would be happy if you let me know if you still have some questions or replies. If so, I will reply promptly. Looking forward to your reply.

Thank you very much for your evaluation of our work. We will now provide detailed responses to the raised questions.

We have made several modifications to the original text, improving the grammar and sentences to enhance the overall readability of the article. For instance, in the introduction of the first chapter, we strengthened the logical flow to make the development of graph masking technology more comprehensible. Regarding Figure 1, we redesigned the information within the image. We added a grid to the background and clarified the numerical values of each point, allowing readers to clearly observe the overall trend.

First and foremost, it is crucial to clarify that the viewpoints presented in the article are derived from prior relevant research and our experimental results. The perspectives in sections 3.1.1 and 3.1.2 are based on references [1] and [2], respectively. These sections were briefly mentioned in Chapter 1 without elaboration, as they are not the focus of this section, to avoid unnecessary repetition. Therefore, in these subsections, we only provide brief mentions. A more detailed explanation is warranted, as we believe in the viewpoint presented in 3.1.1. This is because, when both node features and edges of the same node are masked, we lack direct information about this node and can only obtain its information from the hidden representations of other nodes. This poses a greater obstacle to the originally intended reconstruction decoding. Without alternative decoding methods, it would have a detrimental impact on the model's performance. To validate this point, we conducted experiments. Specifically, we changed the decoding method to reconstruct the graph structure traditionally. This approach did not consider the harmful effects of simultaneously blocking two modal information types. From the experimental results, it is evident that the clustering performance of this reconstruction method significantly deteriorated. We experimented with the Cora dataset.GCMA-r stands for using the traditional reconstruction graph structure as the decoder, and SHOT stands for the number of correct k-values predicted.

Regarding the point mentioned in Section 3.1.2 about GAE overly emphasizing proximity information, this is because previous GAE clustering methods mostly used the link reconstruction graph method to construct loss. In each node's hidden representation, there is information about other neighboring nodes, once again emphasizing the impact of proximity information on overall reconstruction.

As for the point in Section 3.2.1 about re-masking Zm to obtain more compressed representations, this is done because a single masked encoding may not provide comprehensive information for multi-target reconstruction. As the masks are random, using different masked compression representations for the reconstruction of different targets allows our model to learn more diverse modal knowledge content. Additional experiments have been added to demonstrate a significant decrease in experimental performance if we only use a single masked embedding. GCMA-one represents the result under just one mask, and shot represents the number of times the correct k-value was predicted.

Finally, thank you again for taking the time to review my paper and I look forward to hearing from you again.

[1] Jintang Li, et al.What’s behind the mask: Understanding masked graph modeling for graph autoencoders.

[2] Yucheng Shi, et al.Gigamae: Generalizable graph masked autoencoder via collaborative latent space reconstruction.

Dear reviewer, I have submitted my reply a few days ago. Now the deadline for public comment is approaching, but I observe that you have not replied to my comment. I would be happy if you let me know if you still have some questions or replies. If so, I will reply promptly. Looking forward to your reply.

Thank you very much for your evaluation of our work. We will now provide detailed responses to the raised questions.

Our primary contribution lies in the application of graph mask autoencoders for clustering analysis. However, we have not identified any existing non-parametric methods utilizing graph mask autoencoders for clustering analysis. Most clustering models employing self-supervised learning on graphs utilize single-class-based autoencoders, as documented in references [1] and [2]. These references respectively employ GAT and GCN as encoders to construct autoencoder-based deep clustering models. Additionally, certain methods leverage fusion encoders, combining GNN networks and DNN networks, as illustrated in reference [3]. This alignment is also evident in our Table 3, where our chosen baselines are consistent with these methods.

Presently, various masking strategies have evolved in graph mask techniques. The earliest approach, as demonstrated in MGAE, involves initially applying edge masks to the graph followed by decoding through cross-linking. Subsequent methods such as MaskGAE utilize single-edge masks and path masks. More recent models like GiGaMAE and GraphMAE introduce feature masks and heavy masks to enhance training data and achieve superior results. However, current research primarily focuses on investigating the encoding performance of graph mask techniques, with most studies concentrating on downstream tasks such as link prediction and node classification. Notably, there is a dearth of deep learning models specifically applied to clustering tasks. The available data on graph mask methods for deep clustering is limited to a small downstream experiment in GiGaMAE. Unfortunately, this model has not made specific improvements for clustering and exhibits suboptimal experimental performance. Its performance on the Cora dataset is as follows.

As a deep graph clustering model, we innovatively integrate graph mask technology with clustering. Our end-to-end integration of graph mask techniques, utilizing single-edge, node, and heavy masks while incorporating AE encoding, involves setting up a multi-target decoder specifically tailored for clustering tasks. In terms of graph encoding techniques, our distinctiveness lies in the modifications made for clustering tasks. We have incorporated multi-target reconstruction and a second CFSFDP decoder, achieving superior clustering performance while keeping training costs economical. For a specialized deep clustering model, our approach marks the first application of graph mask technology, resulting in more compact graph embeddings.

Regarding the density-based clustering algorithm CFSFDP, despite its earlier proposal, it faces three primary challenges. First, the original algorithm's truncation distance traditionally required manual determination based on empirical experience. Our enhancement addresses this by employing a Gaussian kernel, enabling automatic determination of the truncation distance. Second, the original algorithm necessitates the manual input of the cluster number (k) through observation of internal parameters, constituting a semi-automatic determination of k. In contrast, we directly derive cluster centers by computing parameters $\gamma_i$ and point density. Finally, the original CFSFDP is a standalone algorithm, whereas we seamlessly integrate it into the end-to-end GCMA framework and design a unified loss function for optimization. These improvements position CFSFDP as the second decoder module in GCMA. Consequently, our approach, as a non-parametric method, eliminates the need for pre-inputting the cluster number k. The original method fails to yield results as robust as our improved algorithm. It is noteworthy that in the field of graph clustering, few researchers have explored the application of this method.

[1] Chun Wang, et al.Attributed graph clustering: A deep attentional embedding approach.

[2] Hong Yuan，et al.. Embedding graph auto-encoder for graph clustering

[3] Deyu Bo, et al.. Structural deep clustering network.

Dear reviewer, I have submitted my reply a few days ago. Now the deadline for public comment is approaching, but I observe that you have not replied to my comment. I would be happy if you let me know if you still have some questions or replies. If so, I will reply promptly. Looking forward to your reply.