PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural Deep Clustering Network

Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, Peng Cui

arXiv:2002.01633v3cs.LGstat.ML

TL;DR

Deep clustering methods often learn representations from data characteristics while giving limited attention to sample relationships and higher-order structure. SDCN integrates autoencoder and GCN representations through a delivery operator and dual self-supervision, and consistently outperforms state-of-the-art deep clustering methods across open datasets.

  • Problem

    Deep clustering rarely incorporates the complex low-order and high-order structure among data samples, despite structural information guiding representation learning.

  • Method

    SDCN combines autoencoder and GCN representations with a delivery operator and trains both modules end-to-end through a dual self-supervised framework.

  • Results

    SDCN consistently outperforms state-of-the-art deep clustering methods across various open datasets.

  • Takeaways & Limitations

    The delivery operator integrates multiple-order structural information with autoencoder representations while GCN provides approximate second-order graph regularization and autoencoder representations alleviate GCN over-smoothing.

  • Takeaways & Limitations

    For discrete data such as bag-of-words, dot-product similarity relates similarity only to the number of identical words.

Abstract

from arXiv · show

Clustering is a fundamental task in data analysis. Recently, deep clustering, which derives inspiration primarily from deep learning approaches, achieves state-of-the-art performance and has attracted considerable attention. Current deep clustering methods usually boost the clustering results by means of the powerful representation ability of deep learning, e.g., autoencoder, suggesting that learning an effective representation for clustering is a crucial requirement. The strength of deep clustering methods is to extract the useful representations from the data itself, rather than the structure of data, which receives scarce attention in representation learning. Motivated by the great success of Graph Convolutional Network (GCN) in encoding the graph structure, we propose a Structural Deep Clustering Network (SDCN) to integrate the structural information into deep clustering. Specifically, we design a delivery operator to transfer the representations learned by autoencoder to the corresponding GCN layer, and a dual self-supervised mechanism to unify these two different deep neural architectures and guide the update of the whole model. In this way, the multiple structures of data, from low-order to high-order, are naturally combined with the multiple representations learned by autoencoder. Furthermore, we theoretically analyze the delivery operator, i.e., with the delivery operator, GCN improves the autoencoder-specific representation as a high-order graph regularization constraint and autoencoder helps alleviate the over-smoothing problem in GCN. Through comprehensive experiments, we demonstrate that our propose model can consistently perform better over the state-of-the-art techniques.

1 INTRODUCTION

Deep clustering learns representations from data characteristics but seldom incorporates sample relationships and higher-order structure. SDCN combines autoencoder and GCN representations through a delivery operator and dual self-supervision, outperforming state-of-the-art methods.

  • Motivation: Deep clustering prioritizes powerful learned representations, while structural relationships among samples receive comparatively little attention.Sample relationships can reveal latent similarity and guide representation learning.
  • Motivation: Sparse data require modeling both direct and higher-order relationships, including similarity between samples sharing many neighbors despite no direct link.The paper identifies higher-order structure as especially important when the data structure is sparse.
  • Method: SDCN constructs a KNN graph and uses multiple GCN layers to learn representations containing low-order and high-order structural information.The KNN graph is used to expose the underlying data structure.
  • Method: A delivery operator combines autoencoder-specific and GCN-specific representations, while theoretical analysis links this integration to second-order graph regularization and reduced GCN over-smoothing.The autoencoder representation can alleviate over-smoothing in GCN, while GCN regularizes the autoencoder representation.
  • Method: A dual self-supervised module jointly guides the autoencoder and GCN, enabling end-to-end training for clustering.The mechanism provides a uniform training framework for both modules.

2 RELATED WORK

Related work covers deep clustering methods that combine representation learning with clustering objectives and GCN-based methods that incorporate graph structure into node embeddings. Figure 1 situates SDCN as a framework combining these structural and representation-learning components.

  • Deep clustering: Deep clustering methods combine deep representation learning with clustering objectives, using approaches such as K-means losses or KL-divergence losses.These methods use clustering objectives to shape autoencoder representations and improve cluster cohesion.
  • Graph clustering with GCN: GCN-based clustering methods incorporate graph structure into node features or embeddings, including graph autoencoders and attention-based graph clustering.The related methods use GCNs or neighboring-node attention to model structural information.
  • SDCN framework: Figure 1 depicts SDCN's input and reconstructed data, layerwise DNN and GCN representations, and dual self-supervised updates driven by target distribution P.The framework uses distribution Q to calculate P, which guides both modules.

3 THE PROPOSED MODEL

SDCN integrates autoencoder representations with low- and high-order structural information learned by GCN for deep clustering. A delivery operator connects the modules layer by layer, while dual self-supervision trains them jointly and the analysis links this design to graph regularization and reduced over-smoothing.

  • KNN Graph and GCN Module: SDCN constructs a KNN graph and uses multiple graph convolutional layers to capture low-order and high-order structural information.The graph is built from sample similarities, and the GCN propagates representations through normalized adjacency matrices.
  • DNN Module: The autoencoder learns representations from raw data, while the GCN incorporates relationships among samples into structure-aware representations.The model combines information from the data itself with information encoded by the graph structure.
  • Delivery Operator: The delivery operator transfers each autoencoder-layer representation into its corresponding GCN layer, combining the two representations before graph propagation.It is applied L times, with balance coefficient ϵ set uniformly to 0.5 in the described implementation.
  • Dual Self-Supervised Module: A dual self-supervised module unifies the autoencoder and GCN in one end-to-end clustering framework by making both modules approximate the same target distribution.The objective uses KL divergence to update the model gently and encourage consistency between the DNN and GCN outputs.
  • Clustering Objective: SDCN uses a Student’s t-distribution to form soft cluster assignments and a softmax-based final GCN classification layer.The assignment probability qij measures similarity between representation hi and cluster center µj, with centers initialized by K-means on pretrained autoencoder representations.
  • Theory Analysis: The theory shows that GCN supplies approximate second-order graph regularization, while SDCN representations combine different-order structural information and alleviate GCN over-smoothing.The delivery operator gives different representations to different-order adjacency information rather than reusing one representation for all orders.

4 EXPERIMENTS

SDCN is evaluated on six datasets spanning image, sensor, text, and paper-network data, with results reported as mean±std clustering metrics.

  • Datasets: SDCN is evaluated on six datasets, including USPS handwritten digits, HHAR activity records, Reuters documents, and ACM2 paper networks.The supplied passages identify these dataset types and examples; Table 2 reports results across six datasets.
  • Evaluation: Table 2 reports clustering results on six datasets as mean±std, highlighting the best results and the best baseline results separately.

4.2 Baselines

The evaluation compares raw-data clustering, deep neural network clustering, and graph-based clustering using four standard metrics under specified training settings.

  • Baselines: The baselines comprise raw-data K-means, autoencoder-based AE, DEC, and IDEC, plus graph methods including GAE, VGAE, and DAEGC.
  • Metrics: Evaluation uses ACC, NMI, ARI, and macro F1, with larger values indicating better clustering results.
  • Parameter Setting: DNN-based clustering methods use pretrained autoencoders, while SDCN trains its autoencoder end-to-end for 30 epochs at learning rate 10^-3.

4.3 Analysis of Clustering Results

Across six datasets, SDCN and SDCNQ achieve the best results for every metric, while graph quality affects the relative performance of structural variants and baselines.

  • Overall Results: SDCN and SDCNQ achieve the best result for every metric on all six datasets.
  • Overall Results: 6% ACC, 17% NMI, and 28% ARI are the average improvements over the best baseline results.
  • Structural Quality: SDCN generally outperforms SDCNQ, but SDCNQ performs much better than SDCN on Reuters because the KNN graph contains many cross-class connections.
  • Loss Analysis: The clustering loss improves cohesion by bringing data representations closer to cluster centers, benefiting both autoencoder- and GCN-based methods.

4.4 Analysis of Variants

Variant analyses examine the delivery operator and GCN against matched alternatives, showing that both contribute to clustering quality across graph settings.

  • Variants: SDCN-w/o removes the delivery operator, whereas SDCN-MLP replaces GCN with an equally deep multilayer perceptron.
  • KNN Graphs: On KNN-graph datasets, SDCN outperforms SDCN-MLP and SDCN-w/o, while SDCN-MLP exceeds SDCN-w/o on Reuters and is similar on USPS and HHAR.
  • Original Graphs: On original-graph datasets, SDCN-w/o outperforms SDCN-MLP, while SDCN remains better than SDCN-w/o.
  • Overall Variant Comparison: Across both dataset types, SDCN achieves the best performance compared with SDCN-w/o and SDCN-MLP.

4.5 Analysis of Different Propagation Layers

Increasing the propagation depth generally improves SDCN clustering, with four GCN layers performing best across the three datasets; three layers underperform two layers because of representation and over-smoothing issues.

  • SDCN-2, SDCN-3, and SDCN-4 consistently improve over SDCN-1 across all datasets.
  • SDCN-4 outperforms the other methods on all three datasets.
  • SDCN-3 performs worse than SDCN-2 because it transfers transitional H(2) representations and remains affected by over-smoothing.H(2) loses some underlying information while lacking semantic information, and insufficient GCN depth leaves the over-smoothing term too large.
  • The authors argue that all autoencoder-layer representations should be transferred to corresponding GCN layers to preserve information.

4.6 Analysis of balance coefficient ϵ

SDCN performs best with a balanced contribution from its GCN and DNN representations, while excluding autoencoder representations causes the worst clustering accuracy. The balance coefficient therefore materially affects performance across datasets.

  • Balance coefficient effects: ϵ = 1.0 makes the GCN use only the DNN representation H(L), removing the autoencoder contribution to the GCN input.
  • Balance coefficient effects: ϵ = 0.5 achieves the best clustering accuracy on Reuters, ACM, DBLP, and Citeseer.This indicates that GCN and DNN representations are both important to SDCN performance.
  • Balance coefficient effects: ϵ = 0.0 performs worst across all datasets because the GCN becomes a standard multilayer GCN with serious over-smoothing.
  • Balance coefficient effects: Even with ϵ = 1.0, SDCN retains some structural information and improves clustering, but its limited number of layers prevents the best results.

4.7 K-sensitivity Analysis

The K-sensitivity experiment evaluates SDCN on KNN-graph datasets across several nearest-neighbor settings and finds that it remains superior to graph-focused baselines.

  • K-sensitivity results: K = {1, 3, 5, 10} yields better SDCN results than GAE, VGAE, and DAEGC on KNN-graph datasets.The experiment is designed to test whether SDCN is insensitive to the nearest-neighbor parameter K.

4.8 Analysis of Training Process

The training-process analysis tracks three sample-assignment distributions over iterations and shows that SDCN-P is usually more accurate than SDCN-Q.

  • Distribution accuracy: SDCN-P, SDCN-Q, and SDCN-Z represent the accuracies of target distributions P, Q, and Z, respectively.
  • Distribution accuracy: In most cases, SDCN-P has higher accuracy than SDCN-Q during training.This comparison concerns the target and auxiliary sample-assignment distributions shown in Figure 4.

5 CONCLUSION

SDCN integrates structural information into deep clustering by combining DNN- and GCN-based representations through a delivery operator and dual self-supervision. The model is theoretically analyzed and consistently outperforms state-of-the-art deep clustering methods on various open datasets.

  • SDCN combines DNN and GCN modules with a dual self-supervised module for structural deep clustering.
  • A delivery operator combines autoencoder-specific and GCN-specific representations, with theoretical analysis demonstrating its integration strength.
  • SDCN consistently outperforms state-of-the-art deep clustering methods across various open datasets.
Loading 2002.01633v3…