Preprint
Robust Deep Signed Graph Clustering via Weak Balance Theory
arXiv , Vol.8 February 2025
Cornell University
2025
Abstract
Signed graph clustering is a critical technique for discovering community structures in graphs that exhibit both positive and negative relationships. We have identified two significant challenges in this domain: i) existing signed spectral methods are highly vulnerable to noise, which is prevalent in real-world scenarios; ii) the guiding principle ``an enemy of my enemy is my friend'', rooted in \textit{Social Balance Theory}, often narrows or disrupts cluster boundaries in mainstream signed graph neural networks. Addressing these challenges, we propose the \underline{D}eep \underline{S}igned \underline{G}raph \underline{C}lustering framework (DSGC), which leverages \textit{Weak Balance Theory} to enhance preprocessing and encoding for robust representation learning. First, DSGC introduces Violation Sign-Refine to denoise the signed network by correcting noisy edges with high-order neighbor information. Subsequently, Density-based Augmentation enhances semantic structures by adding positive edges within clusters and negative edges across clusters, following \textit{Weak Balance} principles. The framework then utilizes \textit{Weak Balance} principles to develop clustering-oriented signed neural networks to broaden cluster boundaries by emphasizing distinctions between negatively linked nodes. Finally, DSGC optimizes clustering assignments by minimizing a regularized clustering loss. Comprehensive experiments on synthetic and real-world datasets demonstrate DSGC consistently outperforms all baselines, establishing a new benchmark in signed graph clustering.
Details
- Title
- Robust Deep Signed Graph Clustering via Weak Balance Theory
- Authors
- Peiyao Zhao - Beijing Institute of TechnologyXin Li - Beijing Institute of TechnologyZeyu Zhang - Huazhong Agricultural UniversityMingzhong Wang - University of the Sunshine Coast, Queensland, School of Science, Technology and EngineeringXueying Zhu - Beijing Institute of TechnologyLejian Liao - Beijing Institute of Technology
- Publication details
- arXiv , Vol.8 February 2025
- Publisher
- Cornell University
- Date published
- 2025
- DOI
- 10.48550/arxiv.2502.05472
- ISSN
- 2331-8422
- Organisation Unit
- School of Science, Technology and Engineering; Healthy Ageing Research Cluster
- Language
- English
- Record Identifier
- 991103735802621
- Output Type
- Preprint
Metrics
4 Record Views