# Deep Cut-informed Graph Embedding and Clustering

arXiv: https://arxiv.org/abs/2503.06635 · HTML: https://mlsanity.com/paper/2503.06635/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 55 references that are in the map.
- First posted on arXiv 9 Mar 2025.

## Builds on (most cited first, 30 of 30)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Learning Graph Embedding with Adversarial Training Methods](https://mlsanity.com/paper/1901.01250/) (2019)
- [Deep Fusion Clustering Network](https://mlsanity.com/paper/2012.09600/) (2020)
- [Attention-driven Graph Clustering Network](https://mlsanity.com/paper/2108.05499/) (2021)
- [A Comprehensive Survey on Data Augmentation](https://mlsanity.com/paper/2405.09591/) (2024)
- [Attributed Network Embedding for Learning in a Dynamic Environment](https://mlsanity.com/paper/1706.01860/) (2017)
- [Improving Sequence-to-Sequence Learning via Optimal Transport](https://mlsanity.com/paper/1901.06283/) (2019)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Word Mover's Embedding: From Word2Vec to Document Embedding](https://mlsanity.com/paper/1811.01713/) (2018)
- [Revisiting Modularity Maximization for Graph Clustering: A Contrastive Learning Perspective](https://mlsanity.com/paper/2406.14288/) (2024)
- [Graph Soft-Contrastive Learning via Neighborhood Ranking](https://mlsanity.com/paper/2209.13964/) (2022)
- [Co-clustering through Optimal Transport](https://mlsanity.com/paper/1705.06189/) (2017)
- [LightCAKE: A Lightweight Framework for Context-Aware Knowledge Graph Embedding](https://mlsanity.com/paper/2102.10826/) (2021)
- [scCDCG: Efficient Deep Structural Clustering for single-cell RNA-seq via Deep Cut-informed Graph Embedding](https://mlsanity.com/paper/2404.06167/) (2024)
- [Contrastive Deep Nonnegative Matrix Factorization for Community Detection](https://mlsanity.com/paper/2311.02357/) (2023)
- [Make Graph Neural Networks Great Again: A Generic Integration Paradigm of Topology-Free Patterns for Traffic Speed Prediction](https://mlsanity.com/paper/2406.16992/) (2024)

## Built on by (most cited first, 7 of 7)

- [scSiameseClu: A Siamese Clustering Framework for Interpreting single-cell RNA Sequencing Data](https://mlsanity.com/paper/2505.12626/) (2025)
- [Rethinking Graph Contrastive Learning through Relative Similarity Preservation](https://mlsanity.com/paper/2505.05533/) (2025)
- [Disentangled Multi-span Evolutionary Network against Temporal Knowledge Graph Reasoning](https://mlsanity.com/paper/2505.14020/) (2025)
- [scCluBench: Comprehensive Benchmarking of Clustering Algorithms for Single-Cell RNA Sequencing](https://mlsanity.com/paper/2512.02471/) (2025)
- [Soft Graph Clustering for single-cell RNA Sequencing Data](https://mlsanity.com/paper/2507.09890/) (2025)
- [Distilling Closed-Source LLM's Knowledge for Locally Stable and Economic Biomedical Entity Linking](https://mlsanity.com/paper/2505.19722/) (2025)
- [Beyond Paper-to-Paper: Structured Profiling and Rubric Scoring for Paper-Reviewer Matching](https://mlsanity.com/paper/2604.05866/) (2026)

## Abstract (arXiv)

Graph clustering aims to divide the graph into different clusters. The recently emerging deep graph clustering approaches are largely built on graph neural networks (GNN). However, GNN is designed for general graph encoding and there is a common issue of representation collapse in existing GNN-based deep graph clustering algorithms. We attribute two main reasons for such issues: (i) the inductive bias of GNN models: GNNs tend to generate similar representations for proximal nodes. Since graphs often contain a non-negligible amount of inter-cluster links, the bias results in error message passing and leads to biased clustering; (ii) the clustering guided loss function: most traditional approaches strive to make all samples closer to pre-learned cluster centers, which causes a degenerate solution assigning all data points to a single label thus making all samples similar and less discriminative. To address these challenges, we investigate graph clustering from a graph cut perspective and propose an innovative and non-GNN-based Deep Cut-informed Graph embedding and Clustering framework, namely DCGC. This framework includes two modules: (i) cut-informed graph encoding; (ii) self-supervised graph clustering via optimal transport. For the encoding module, we derive a cut-informed graph embedding objective to fuse graph structure and attributes by minimizing their joint normalized cut. For the clustering module, we utilize the optimal transport theory to obtain the clustering assignments, which can balance the guidance of "proximity to the pre-learned cluster center". With the above two tailored designs, DCGC is more suitable for the graph clustering task, which can effectively alleviate the problem of representation collapse and achieve better performance. We conduct extensive experiments to demonstrate that our method is simple but effective compared with benchmarks.