# Effective Clustering for Large Multi-Relational Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 114 references that are in the map.
- First posted on arXiv 24 Aug 2025.

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

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (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)
- [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)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Adaptive Graph Encoder for Attributed Graph Embedding](https://mlsanity.com/paper/2007.01594/) (2020)
- [Multi-view Contrastive Graph Clustering](https://mlsanity.com/paper/2110.11842/) (2021)
- [Large-scale Multi-view Subspace Clustering in Linear Time](https://mlsanity.com/paper/1911.09290/) (2019)
- [Cluster-guided Contrastive Graph Clustering Network](https://mlsanity.com/paper/2301.01098/) (2023)
- [Graph Embedding on Biomedical Networks: Methods, Applications, and Evaluations](https://mlsanity.com/paper/1906.05017/) (2019)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource](https://mlsanity.com/paper/2211.12875/) (2022)
- [PANE: scalable and effective attributed network embedding](https://mlsanity.com/paper/2009.00826/) (2020)
- [DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization](https://mlsanity.com/paper/2312.12697/) (2023)
- [Clustering attributed graphs: models, measures and methods](https://mlsanity.com/paper/1501.01676/) (2015)
- [Deep Multi-View Subspace Clustering with Anchor Graph](https://mlsanity.com/paper/2305.06939/) (2023)
- [CaEGCN: Cross-Attention Fusion based Enhanced Graph Convolutional Network for Clustering](https://mlsanity.com/paper/2101.06883/) (2021)
- [Upper Bounding Barlow Twins: A Novel Filter for Multi-Relational Clustering](https://mlsanity.com/paper/2312.14066/) (2023)
- [Beyond Redundancy: Information-aware Unsupervised Multiplex Graph Structure Learning](https://mlsanity.com/paper/2409.17386/) (2024)
- [Efficient High-Quality Clustering for Large Bipartite Graphs](https://mlsanity.com/paper/2312.16926/) (2023)
- [Effective and Scalable Clustering on Massive Attributed Graphs](https://mlsanity.com/paper/2102.03826/) (2021)
- [Balanced Multi-Relational Graph Clustering](https://mlsanity.com/paper/2407.16863/) (2024)
- [Multilayer Graph Contrastive Clustering Network](https://mlsanity.com/paper/2112.14021/) (2021)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)

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

- [SNAP-KG: Streaming Node Assignment via Projection for Knowledge Graph Entity Integration](https://mlsanity.com/paper/2608.25149/) (2026)
- [GCN-MPPR: Enhancing the Propagation of Message Passing Neural Networks via Motif-Based Personalized PageRank](https://mlsanity.com/paper/2602.07903/) (2026)

## Abstract (arXiv)

Multi-relational graphs (MRGs) are an expressive data structure for modeling diverse interactions/relations among real objects (i.e., nodes), which pervade extensive applications and scenarios. Given an MRG G with N nodes, partitioning the node set therein into K disjoint clusters (MRGC) is a fundamental task in analyzing MRGs, which has garnered considerable attention. However, the majority of existing solutions towards MRGC either yield severely compromised result quality by ineffective fusion of heterogeneous graph structures and attributes, or struggle to cope with sizable MRGs with millions of nodes and billions of edges due to the adoption of sophisticated and costly deep learning models. In this paper, we present DEMM and DEMM+, two effective MRGC approaches to address the limitations above. Specifically, our algorithms are built on novel two-stage optimization objectives, where the former seeks to derive high-caliber node feature vectors by optimizing the multi-relational Dirichlet energy specialized for MRGs, while the latter minimizes the Dirichlet energy of clustering results over the node affinity graph. In particular, DEMM+ achieves significantly higher scalability and efficiency over our based method DEMM through a suite of well-thought-out optimizations. Key technical contributions include (i) a highly efficient approximation solver for constructing node feature vectors, and (ii) a theoretically-grounded problem transformation with carefully-crafted techniques that enable linear-time clustering without explicitly materializing the NxN dense affinity matrix. Further, we extend DEMM+ to handle attribute-less MRGs through non-trivial adaptations. Extensive experiments, comparing DEMM+ against 20 baselines over 11 real MRGs, exhibit that DEMM+ is consistently superior in terms of clustering quality measured against ground-truth labels, while often being remarkably faster.