PaperlayerView exact revision on arXiv

Source-linked AI summary

Simple Contrastive Graph Clustering

Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu

arXiv:2205.07865v3cs.LGcs.AI

TL;DR

Existing contrastive deep graph clustering methods face efficiency problems from complex graph augmentations and time-consuming graph convolutions. SCGC addresses these issues with independent low-pass preprocessing, two MLP-based siamese encoders, direct embedding perturbation, and a cross-view structural consistency objective; on seven benchmark datasets, it is reported to outperform recent contrastive competitors with at least seven times speedup on average.

  • Problem

    Complex graph augmentations and time-consuming graph convolutions undermine the efficiency of existing contrastive deep graph clustering methods.

  • Method

    SCGC combines independent low-pass neighborhood aggregation, two parameter-unshared MLP encoders with direct embedding perturbation, and a neighbor-oriented cross-view structural consistency objective.

  • Results

    On seven benchmark datasets, SCGC outperforms recent contrastive deep clustering competitors with at least seven times speedup on average.

  • Takeaways & Limitations

    SCGC is free from pre-training and saves time and space for network training while retaining reported clustering effectiveness and superiority.

Abstract

from arXiv · show

Contrastive learning has recently attracted plenty of attention in deep graph clustering for its promising performance. However, complicated data augmentations and time-consuming graph convolutional operation undermine the efficiency of these methods. To solve this problem, we propose a Simple Contrastive Graph Clustering (SCGC) algorithm to improve the existing methods from the perspectives of network architecture, data augmentation, and objective function. As to the architecture, our network includes two main parts, i.e., pre-processing and network backbone. A simple low-pass denoising operation conducts neighbor information aggregation as an independent pre-processing, and only two multilayer perceptrons (MLPs) are included as the backbone. For data augmentation, instead of introducing complex operations over graphs, we construct two augmented views of the same vertex by designing parameter un-shared siamese encoders and corrupting the node embeddings directly. Finally, as to the objective function, to further improve the clustering performance, a novel cross-view structural consistency objective function is designed to enhance the discriminative capability of the learned network. Extensive experimental results on seven benchmark datasets validate our proposed algorithm's effectiveness and superiority. Significantly, our algorithm outperforms the recent contrastive deep clustering competitors with at least seven times speedup on average.

I. INTRODUCTION

Deep graph clustering methods increasingly use contrastive learning, but complex graph augmentations and graph convolutions reduce efficiency. SCGC addresses these issues with a simpler architecture, attribute-space perturbation, and a neighbor-oriented contrastive objective.

  • Motivation: Contrastive graph clustering improves representations, but complicated data augmentations and time-consuming graph convolutions make existing methods computationally expensive.The efficiency limitation is explicitly identified for recent contrastive methods.
  • Network architecture: SCGC uses a siamese backbone with MLP sub-branches and performs neighborhood aggregation independently before network training.This architecture is intended to improve both clustering performance and training efficiency.
  • Data augmentation: SCGC constructs augmented views by perturbing node embeddings in enhanced attribute space rather than modifying graph structures.The proposed augmentation is reported as compatible with existing contrastive methods.
  • Objective function: A neighbor-oriented contrastive loss preserves structural consistency across views and improves the network's discriminative capability.The objective uses cross-view structural information to guide representation learning.
  • Experiments: Seven benchmark datasets are used to demonstrate SCGC's effectiveness and superiority against existing deep graph clustering competitors.The supplied passages state the evaluation scope but do not provide dataset-level metric values.

A. Deep Graph Clustering

Deep graph clustering divides graph nodes into disjoint groups using learned representations that exploit attributes and structure. Existing approaches include generative, adversarial, and contrastive methods, while SCGC is positioned within the contrastive category.

  • Deep Graph Clustering: Deep graph clustering aims to reveal graph structure and divide nodes into several disjoint groups in an unsupervised manner.A neural network encodes nodes from attributes and structural information before clustering is applied.
  • Deep Graph Clustering: Existing deep graph clustering methods are categorized as generative, adversarial, or contrastive according to their learning mechanisms.The categories differ in how they learn representations or construct training signals.
  • Related Methods: Clustering-guided losses make many earlier methods dependent on good initial cluster centers, leading to pre-training and reduced performance consistency.The supplied passage also connects this dependence with reduced implementation convenience.
  • Contrastive Deep Graph Clustering: Contrastive methods increasingly replace clustering-guided losses, while their performance depends substantially on data augmentation, architecture, and objective-function design.Existing augmentations build views through complex graph operations, motivating comparison with SCGC.
  • Contrastive Deep Graph Clustering: SCGC uses a neighbor-oriented contrastive loss to preserve structural consistency across views and enhance discriminative capability.This distinguishes its objective from representative contrastive alternatives described in the related-work discussion.
  • Notations and Problem Definition: The graph is represented by attribute matrix X and adjacency matrix A, with learned embeddings E subsequently partitioned into k disjoint groups.The supplied notation passages define X and A and describe clustering the learned embeddings.

B. Overall Framework

SCGC consists of a low-pass denoising operation and a Structural Contrastive Module. These components separate neighborhood aggregation from the contrastive network framework.

  • Overall Framework: The SCGC framework has two components: a low-pass denoising operation and a Structural Contrastive Module.The paper details these components together with the objective function.

C. Low-pass Denoising Operation

SCGC first applies independent low-pass denoising to aggregate neighborhood information and filter high-frequency attribute noise. Its structural contrastive module then creates two directly perturbed embedding views and enforces cross-view structural consistency.

  • Low-pass Denoising Operation: The low-pass denoising operation independently aggregates neighborhood information before training and filters high-frequency noise from node attributes.It uses stacked graph Laplacian filters to produce smoothed attributes Xs.
  • Structural Contrastive Module: The smoothed attributes are encoded by two MLPs with identical architectures but un-shared parameters, producing views with different semantic information.The embeddings are normalized with the ℓ2-norm before augmentation.
  • Structural Contrastive Module: SCGC constructs augmented views by adding random Gaussian noise directly to node embeddings rather than applying complex graph operations.The noise is sampled from a Gaussian distribution N(0, σ).
  • Structural Contrastive Module: The neighbor-oriented contrastive loss compares cross-view embeddings through a sample similarity matrix and preserves structural consistency.The similarity matrix S is formed between the two views and aligned with the self-looped adjacency matrix.
  • Structural Contrastive Module: Cross-view neighbors are treated as positive samples and non-neighbors as negative samples, pulling positives together while separating negatives.The objective uses these relationships to enhance the network’s discriminative capability.

E. Fusion and Clustering

SCGC linearly fuses its two augmented node-embedding views into clustering-oriented representations, then applies K-means to obtain cluster assignments.

  • Fusion and Clustering: The two augmented node-embedding views are first fused linearly into resultant clustering-oriented embeddings Z.Z contains the representations used for the final clustering step.
  • Fusion and Clustering: K-means is performed directly on Z to obtain the clustering results.

F. Objective Function

SCGC trains by minimizing a neighbor-oriented contrastive loss with the Adam optimizer, following the learning process specified in Algorithm 1.

  • Objective Function: The proposed method minimizes the neighbor-oriented contrastive loss L in Eq. (8) during training.Adam is used as the optimization algorithm, and Algorithm 1 provides the detailed learning process.

IV. EXPERIMENT

SCGC is evaluated for effectiveness and efficiency on seven benchmark datasets using standard clustering metrics and repeated experimental runs. The experiments specify the implementation, training, parameter, and evaluation settings.

  • Dataset and Evaluation: The evaluation covers seven benchmark datasets: CORA, CITESEER, BAT, EAT, UAT, AMAP, and CORAFULL.Their brief dataset information is summarized in Table IV.
  • Experimental Protocol: All compared results are reported as mean±std over ten runs, with red and blue values marking the best and runner-up results.OOM denotes out-of-memory during training.
  • Training Procedure: SCGC trains for 400 epochs with Adam and applies K-means to the learned clustering-oriented embeddings after optimization.Ten runs are conducted for all compared methods to reduce the influence of randomness.
  • Parameter Settings: The implementation uses two single 500-dimensional embedding-layer MLPs and dataset-specific learning rates.Experiments run on an Intel Core i7-6800K system with an NVIDIA GeForce RTX 3090 GPU, 64GB RAM, and PyTorch.
  • Metrics: Clustering performance is evaluated with ACC, NMI, ARI, and F1.These are the four reported metrics used to compare SCGC with baselines.

C. Performance Comparison

SCGC consistently outperforms the compared clustering methods across seven datasets while reducing training time and GPU memory costs. Its efficiency comes from a lightweight MLP architecture and independently performed low-pass neighbor aggregation.

  • Clustering performance: SCGC consistently outperforms all baselines across seven datasets when averaging ACC, NMI, ARI, and F1.On BAT, it exceeds ARGA by 10.11% ACC, 3.82% NMI, 8.62% ARI, and 11.01% F1.
  • Training efficiency: SCGC achieves the fastest training speed on six datasets and at least seven times average speedup over recent contrastive deep clustering competitors.The comparison trains all methods for 400 epochs.
  • Architecture: The architecture decouples graph convolution from training by applying low-pass denoising as independent neighbor-information preprocessing.This simplifies the training process and filters high-frequency noise in node attributes.
  • Memory efficiency: SCGC saves about 59% GPU memory on average compared with contrastive methods while remaining comparable to classical deep graph clustering methods.Its light siamese MLP encoders and latent-space augmentation reduce memory use.

E. Ablation Studies

Ablation studies support the effectiveness of SCGC's low-pass denoising, structural contrastive module, and latent-space augmentation. Both augmentation components improve clustering, with their combination performing best.

  • Low-pass denoising and SCM: 10.77% average ACC improvement is obtained by adding low-pass denoising across six datasets.The comparison is between L+SCM and the variant without L.
  • Low-pass denoising and SCM: 17.78% average ACC improvement is obtained by adding the Structural Contrastive Module compared with the variant without SCM.The module enhances sample discriminability according to the ablation analysis.
  • Data augmentation: Un-shared siamese MLPs and Gaussian noise each improve clustering performance, while their combination achieves the best performance.Both strategies construct different views of the same node by perturbing latent node embeddings.
  • Data augmentation: SCGC's data augmentation is transferred to MVGRL, GRACE, and GCA to test its compatibility with existing contrastive methods.The supplied passage reports compatibility overall, with exceptions for GRACE on EAT and MVGRL on BAT.

F. Sensitivity Analysis of Hyper-parameters

SCGC performs best with a moderate graph-Laplacian filter depth and remains robust across a bounded Gaussian-noise range. One MLP layer is reported as optimal in the MLP-depth analysis.

  • Graph-Laplacian filter depth: SCGC achieves promising performance when the graph-Laplacian filter layer number t is 2 or 3.The model becomes insensitive to t when 3<t≤5.
  • Gaussian-noise sensitivity: SCGC is robust to Gaussian-noise parameter σ when σ is within [0.001, 0.1].Performance decreases drastically when σ>0.1, attributed to node-embedding semantic drift; σ is set to 0.01.
  • MLP depth: One MLP layer yields the best performance in the MLP-depth analysis.The zero-layer case directly clusters the smoothed attributes, while MLP encoders improve clustering performance.

G. Visualization Analysis

SCGC’s visualization analyses examine embedding structure on CORA and AMAP alongside augmentation transfer, noise sensitivity, and MLP-depth effects. On CORA and AMAP, SCGC more clearly reveals intrinsic clustering structure than six compared baselines.

  • Augmentation transfer: Figure 5 evaluates transferring SCGC’s augmentation fashion to GCA, GRACE, and MVGRL.
  • Noise sensitivity: Figure 6 analyzes the sensitivity of Gaussian-noise standard deviation σ across six datasets.
  • 2D visualization: SCGC embeddings better reveal intrinsic clustering structure than six compared baselines on CORA and AMAP in t-SNE visualizations.The first visualization row corresponds to CORA and the second to AMAP.
  • MLP depth: Figure 8 analyzes how the number of MLP layers affects SCGC.
Loading 2205.07865v3…