# Balanced Multi-Relational Graph Clustering

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 23 Jul 2024.

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

- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [What Makes Training Multi-Modal Classification Networks Hard?](https://mlsanity.com/paper/1905.12681/) (2019)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding](https://mlsanity.com/paper/2002.01680/) (2020)
- [Balanced Multimodal Learning via On-the-fly Gradient Modulation](https://mlsanity.com/paper/2203.15332/) (2022)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Trusted Multi-View Classification with Dynamic Evidential Fusion](https://mlsanity.com/paper/2204.11423/) (2022)
- [What Makes Multi-modal Learning Better than Single (Provably)](https://mlsanity.com/paper/2106.04538/) (2021)
- [PMR: Prototypical Modal Rebalance for Multimodal Learning](https://mlsanity.com/paper/2211.07089/) (2022)
- [Deep Graph Clustering via Dual Correlation Reduction](https://mlsanity.com/paper/2112.14772/) (2021)
- [Unsupervised Attributed Multiplex Network Embedding](https://mlsanity.com/paper/1911.06750/) (2019)
- [HDMI: High-order Deep Multiplex Infomax](https://mlsanity.com/paper/2102.07810/) (2021)
- [Deep Fusion Clustering Network](https://mlsanity.com/paper/2012.09600/) (2020)
- [An Attention-based Collaboration Framework for Multi-View Network Representation Learning](https://mlsanity.com/paper/1709.06636/) (2017)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [Relation Structure-Aware Heterogeneous Information Network Embedding](https://mlsanity.com/paper/1905.08027/) (2019)
- [Simplified Graph Convolution with Heterophily](https://mlsanity.com/paper/2202.04139/) (2022)
- [Upper Bounding Barlow Twins: A Novel Filter for Multi-Relational Clustering](https://mlsanity.com/paper/2312.14066/) (2023)
- [High-order Multi-view Clustering for Generic Data](https://mlsanity.com/paper/2209.10838/) (2022)
- [Unsupervised Multiplex Graph Learning with Complementary and Consistent Information](https://mlsanity.com/paper/2308.01606/) (2023)

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

- [When Heterophily Meets Heterogeneous Graphs: Latent Graphs Guided Unsupervised Representation Learning](https://mlsanity.com/paper/2409.00687/) (2024)
- [Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning](https://mlsanity.com/paper/2409.17386/) (2024)
- [Homophily Enhanced Graph Domain Adaptation](https://mlsanity.com/paper/2505.20089/) (2025)
- [Cooperation of Experts: Fusing Heterogeneous Information with Large Margin](https://mlsanity.com/paper/2505.20853/) (2025)
- [Effective Clustering for Large Multi-Relational Graphs](https://mlsanity.com/paper/2508.17388/) (2025)
- [Multi-Relation Graph-Kernel Strengthen Network for Graph-Level Clustering](https://mlsanity.com/paper/2504.01605/) (2025)
- [Beyond the Academic Monoculture: A Unified Framework and Industrial Perspective for Attributed Graph Clustering](https://mlsanity.com/paper/2603.20829/) (2026)
- [SNAP-KG: Streaming Node Assignment via Projection for Knowledge Graph Entity Integration](https://mlsanity.com/paper/2608.25149/) (2026)
- [AdaMuS: Adaptive Multi-view Sparsity Learning for Dimensionally Unbalanced Data](https://mlsanity.com/paper/2603.17610/) (2026)
- [When Connected Does Not Mean Similar: Charting the Homophily Boundary of SNAP-KG for Streaming Entity Integration](https://mlsanity.com/paper/2609.12356/) (2026)

## Abstract (arXiv)

Multi-relational graph clustering has demonstrated remarkable success in uncovering underlying patterns in complex networks. Representative methods manage to align different views motivated by advances in contrastive learning. Our empirical study finds the pervasive presence of imbalance in real-world graphs, which is in principle contradictory to the motivation of alignment. In this paper, we first propose a novel metric, the Aggregation Class Distance, to empirically quantify structural disparities among different graphs. To address the challenge of view imbalance, we propose Balanced Multi-Relational Graph Clustering (BMGC), comprising unsupervised dominant view mining and dual signals guided representation learning. It dynamically mines the dominant view throughout the training process, synergistically improving clustering performance with representation learning. Theoretical analysis ensures the effectiveness of dominant view mining. Extensive experiments and in-depth analysis on real-world and synthetic datasets showcase that BMGC achieves state-of-the-art performance, underscoring its superiority in addressing the view imbalance inherent in multi-relational graphs. The source code and datasets are available at https://github.com/zxlearningdeep/BMGC.