Multi-level Graph Contrastive Prototypical Clustering

Yuchao Zhang, Yuan Yuan, Qi WangIJCAI 2023 · DOI

Introduction

Graph clustering is a fundamental task in unsupervised learning, aimed at grouping nodes with similar semantic properties without the aid of labels. While Graph Neural Networks (GNNs) have revolutionized graph representation learning by aggregating local neighborhood information, their application to clustering often falls short of capturing global semantic structures. At IJCAI-23, researchers introduced Multi-level Graph Contrastive Prototypical Clustering (MLG-CPC), a novel framework designed to bridge this gap by contrasting representations across three distinct levels: features, prototypes, and clusters.

The Challenges of Graph Clustering

Current deep graph clustering methods face two primary obstacles:

  1. Semantic Agnosticism: Standard GNNs focus on local connectivity. However, nodes belonging to the same semantic class might be topologically distant. Furthermore, traditional contrastive learning often suffers from sampling bias, where it indiscriminately pushes away all "negative" nodes, even those that should belong to the same cluster.
  2. Objective Conflict: Many existing models attempt to optimize multiple objectives (such as graph reconstruction and clustering) within a single latent space. This often results in a "tug-of-war" between competing goals, leading to suboptimal performance.

The MLG-CPC Framework

MLG-CPC addresses these issues by decoupling the optimization objectives into separate spaces. The framework processes two augmented views of the same graph—generated via edge dropping and feature masking—through a multi-level pipeline.

The MLG-CPC architecture, illustrating the multi-level contrastive pipeline across features, prototypes, and cluster assignments.

The pipeline consists of three hierarchical levels:

  • Feature-Level (Orthogonality): The model ensures that node features are augmentation-invariant and non-degenerate. A feature decorrelation loss forces different feature dimensions to be orthogonal, preventing the model from collapsing into redundant representations.
  • Prototypical-Level (Global View): Instead of simple node-to-node comparisons, the model calculates prototypes (centroids) for each cluster. Through Prototype Discrimination (ProDisc), it encourages prototypes of the same cluster across different views to be similar while pushing different cluster prototypes apart, thereby capturing the graph's global semantic structure.
  • Cluster-Level (Consistency): Finally, the model ensures that cluster assignments are consistent across views. By treating assignments as probability distributions and using cross-entropy variants for alignment, it achieves end-to-end semantic consistency.

Key Insights and Experimental Results

A key strength of MLG-CPC is its ability to avoid objective conflict. Because the three levels operate in their own spaces, they can be optimized simultaneously without complex hyper-parameter tuning.

Similarity matrix visualization demonstrating the effect of feature orthogonalization, resulting in a clean diagonal structure.

The effectiveness of this approach is evident in the visualization of similarity matrices. Forcing feature orthogonality leads to a distinct diagonal structure, indicating that the model learns non-redundant, discriminative characteristics for each cluster.

In empirical evaluations across four major benchmarks (ACM, DBLP, CITE, and AMAP), MLG-CPC consistently outperformed 12 state-of-the-art baselines. For instance, on the ACM dataset, it achieved an accuracy (ACC) of 93.20%, surpassing previous methods. Ablation studies further confirmed that all three levels are essential, with the cluster-level consistency being particularly vital for final performance.

Conclusion

MLG-CPC represents a significant step forward in deep graph clustering by moving beyond local neighborhood analysis toward a global semantic understanding. By separating feature, prototype, and cluster objectives, it avoids common optimization pitfalls and sets a new standard for performance on homophilic graph benchmarks. Future research will explore the framework's adaptability to heterophilic graphs, where connected nodes often belong to different classes.

Summary updated

BibTeX
@inproceedings{zhang2023multi,
  author = {Yuchao Zhang and Yuan Yuan and Qi Wang},
  title = {{Multi-level Graph Contrastive Prototypical Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/513},
}
Figure