Deep Cut-informed Graph Embedding and Clustering

Zhiyuan Ning, Zaitian Wang, Ran Zhang, Ping Xu, Kunpeng Liu, Pengyang Wang, Wei Ju, Pengfei Wang, Yuanchun Zhou, Erik Cambria, Chong Chen · 2025

Read Deep Cut-informed Graph Embedding and Clustering by Zhiyuan Ning, Zaitian Wang, Ran Zhang, Ping Xu, Kunpeng Liu, Pengyang Wang, Wei Ju, Pengfei Wang, Yuanchun Zhou, Erik Cambria, Chong Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06635.txt.

Introduction

Zhiyuan Ning and ten co-authors present, in 2025 work, a new way to sort linked data into groups. Such data form nets, where points join by lines. New deep methods often blur the codes of close points, so groups smear and the sort fails. The team traces that flaw to how the nets pass news along their links.

Their fix skips the usual net layers. One part builds codes by a cut rule that weighs both links and traits of each point. The next part assigns groups with a transport method that stops all points from being dumped in one group. Tests against rival methods, the team reports, show strong results with a simple design. They frame the cut view as a better base for the task.

Catalog record

CREATORZhiyuan Ning, Zaitian Wang, Ran Zhang, Ping Xu, Kunpeng Liu, Pengyang Wang, Wei Ju, Pengfei Wang, Yuanchun Zhou, Erik Cambria, Chong Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE54 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06635

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deep Cut-informed Graph Embedding and Clustering Zhiyuan Ning, Zaitian Wang, Ran Zhang, Ping Xu, Kunpeng Liu, Pengyang Wang, Wei Ju, Pengfei Wang, Yuanchun Zhou, Erik Cambria, Chong Chen Abstract 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 D eep C ut-informed G raph embedding and C lustering 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. Journal: Information Fusion † † highlights: Investigate graph clustering from a graph cut perspective. Proposing a novel and non-GNN-based graph clustering paradigm, DCGC. A cut-informed graph encoding module to fuse graph structure and node attributes. Self-supervised graph clustering via optimal transport. (a) GNN-based (b) Cut-informed Figure 1: The motivation of our deep cut-informed graph embedding and clustering: (a) the GNN-based methods can lead to error message passing when noisy links exist. (b) Our cut-informed approach learns embeddings corresponding to minimal normalized cut. 1 Introduction Graph clustering is a fundamental task that has attracted intensive attention and achieved great success on many fields, such as co-saliency and community detection [ 1 , 2 , 3 ] . Beside graph structure, each sample/node is usually accompanied with attributes, such as keywords in citation networks and covariates in social networks. Many researchers have paid attention to combining the graph structure and node attributes to elevate graph clustering performances. Recently, with the emergence of deep learning [ 4 , 5 ] , deep graph clustering has become a rapidly evolving research area, which addresses the task of training neural networks to learn representations and partitioning nodes in attribute graphs into distinct groups. Promising improvements have been made compared with conventional methods in such an unsupervised mission through utilizing deep neural networks, particularly graph neural networks (GNNs) [ 6 , 7 , 8 ] . These models typically embed nodes into the hidden space and then perform clustering algorithms. In particular, the work in [ 9 ] jointly considered the local structure preservation in deep clustering, optimizing cluster assignments and learning features by integrating the clustering loss and auto-encoder reconstruction loss. The work in [ 10 ] designed a delivery operator and a dual self-supervised mechanism to combine the auto-encoder representation and the graph convolutional networks (GCNs) [ 6 ] representation. The work in [ 11 ] proposed a dynamic cross-modality fusion mechanism and a triplet self-supervised strategy, etc. They all focus on developing sophisticated graph neural networks to fuse graph structure and node attributes to learn a general representation of graph topology (e.g., global, local, neighbor, subgraph) and attributes. Despite achieving commendable performance, there is a common issue in existing GNN-based deep graph clustering algorithms. Specifically, these algorithms often encounter the problem of representation collapse [ 12 ] , wherein nodes belonging to distinct categories are frequently mapped to similar representations during the sample encoding process. Consequently, the resulting node representations lack discrimination, leading to limited efficacy in clustering performance. The issue of representation collapse remains unresolved, which is restricting the performance of deep graph clustering algorithms that rely on GNNs [ 12 , 13 ] . We attribute two main reasons for the representation collapse problem of GNN-based deep graph clustering algorithms: (i) The inductive bias of GNNs : Many existing GNNs have the inductive bias that linked nodes typically belong to the same class or have similar characteristics [ 14 ] . Such inductive bias makes GNN representations similar for nodes in close proximity [ 15 ] . When the GNNs get deeper , the inductive bias will even lead to the over-smoothing issue (indistinguishable representations of nodes in different classes) [ 16 ] . So when faced with graph clustering, an unsupervised learning task without any labeling information, the problem caused by the inductive bias of GNN models will become more severe. Besides, the graph structure usually contains a non-negligible amount of inter-cluster links. For example, citation networks usually have cross-subject links (e.g., Figure 1a ). According to the inductive bias, the GNN-based clustering methods may make the node embeddings from different clusters similar, because there may exist error message passing [ 17 ] through the inter-cluster links (i.e., red lines in Figure 1a ). Thus, it is urgent to design a new method to reduce the effects of error propagation caused by GNNs’ inductive bias. (ii) The clustering guided loss function : Most traditional approaches adopt a clustering guided loss function [ 18 ] to force the generated sample embeddings to have the minimum distortion against the pre-learned clustering centers. They typically strive to minimize the distance between data representations and pre-learned cluster centers, thereby enhancing cluster cohesion [ 19 , 20 , 10 , 21 ] . However, making all samples much closer to cluster centers may cause a degenerate solution that assigns all data points to a single (arbitrary) label, thus making all samples similar and less discriminative [ 12 ] . Therefore, we need to design a mechanism to balance the guidance of “proximity to the pre-learned cluster center". To tackle the above-mentioned issues, we propose a novel and non-GNN-based graph clustering paradigm named D eep C ut-informed G raph embedding and C lustering framework (DCGC). This paradigm includes two modules: (i) cut-informed graph encoding , which does not use any GNN-based model as graph encoder and designs the core module from a perspective (i.e., graph cut) that is more reasonable and appropriate for the graph clustering task, therefore avoids the problems caused by the inductive bias of GNN models; (ii) self-supervised graph clustering via optimal transport , which balances the guidance of “proximity to the pre-learned cluster center” via optimal transport, thus avoiding the degenerate solutions. Specifically, for the cut-informed graph encoding module, we show that the normalized cut [ 22 ] minimization can be relaxed into solving k

Read the complete text