# Clustering in graphs and hypergraphs with categorical edge labels

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2019.

## Built on by (most cited first, 30 of 31)

- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [From Hypergraph Energy Functions to Hypergraph Neural Networks](https://mlsanity.com/paper/2306.09623/) (2023)
- [Inference of hyperedges and overlapping communities in hypergraphs](https://mlsanity.com/paper/2204.05646/) (2022)
- [AHP: Learning to Negative Sample for Hyperedge Prediction](https://mlsanity.com/paper/2204.06353/) (2022)
- [Ollivier-Ricci Curvature for Hypergraphs: A Unified Framework](https://mlsanity.com/paper/2210.12048/) (2022)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality](https://mlsanity.com/paper/2411.03331/) (2024)
- [Tackling Over-smoothing on Hypergraphs: A Ricci Flow-guided Neural Diffusion Approach](https://mlsanity.com/paper/2603.15696/) (2026)
- [Hybrid Graph: A Unified Graph Representation with Datasets and Benchmarks for Complex Graphs](https://mlsanity.com/paper/2306.05108/) (2023)
- [Enhancing Hyperedge Prediction with Context-Aware Self-Supervised Learning](https://mlsanity.com/paper/2309.05798/) (2023)
- [Hypergraph Node Representation Learning with One-Stage Message Passing](https://mlsanity.com/paper/2312.00336/) (2023)
- [Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking](https://mlsanity.com/paper/2402.11339/) (2024)
- [Categorical data clustering: 25 years beyond K-modes](https://mlsanity.com/paper/2408.17244/) (2024)
- [BHyGNN+: Unsupervised Representation Learning for Heterophilic Hypergraphs](https://mlsanity.com/paper/2602.14919/) (2026)
- [Heterophily-Agnostic Hypergraph Neural Networks with Riemannian Local Exchanger](https://mlsanity.com/paper/2603.00599/) (2026)
- [Scalable tensor methods for nonuniform hypergraphs](https://mlsanity.com/paper/2306.17825/) (2023)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)
- [MARIOH: Multiplicity-Aware Hypergraph Reconstruction](https://mlsanity.com/paper/2504.00522/) (2025)
- [HyperDet: Source Detection in Hypergraphs via Interactive Relationship Construction and Feature-rich Attention Fusion](https://mlsanity.com/paper/2505.12894/) (2025)
- [SourceDetMamba: A Graph-aware State Space Model for Source Detection in Sequential Hypergraphs](https://mlsanity.com/paper/2505.12910/) (2025)
- [Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach](https://mlsanity.com/paper/2505.18043/) (2025)
- [Lower Ricci Curvature for Hypergraphs](https://mlsanity.com/paper/2506.03943/) (2025)
- [Higher-Order Graph Databases](https://mlsanity.com/paper/2506.19661/) (2025)
- [Implicit Hypergraph Neural Network](https://mlsanity.com/paper/2508.14101/) (2025)
- [Learning Multi-Order Block Structure in Higher-Order Networks](https://mlsanity.com/paper/2511.21350/) (2025)
- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)
- [From Diffusion to Reaction-Diffusion: A Dynamical-Systems View of Oversmoothing in Hypergraph Neural Networks](https://mlsanity.com/paper/2607.15773/) (2026)

## Abstract (arXiv)

Modern graph or network datasets often contain rich structure that goes beyond simple pairwise connections between nodes. This calls for complex representations that can capture, for instance, edges of different types as well as so-called "higher-order interactions" that involve more than two nodes at a time. However, we have fewer rigorous methods that can provide insight from such representations. Here, we develop a computational framework for the problem of clustering hypergraphs with categorical edge labels --- or different interaction types --- where clusters corresponds to groups of nodes that frequently participate in the same type of interaction. Our methodology is based on a combinatorial objective function that is related to correlation clustering on graphs but enables the design of much more efficient algorithms that also seamlessly generalize to hypergraphs. When there are only two label types, our objective can be optimized in polynomial time, using an algorithm based on minimum cuts. Minimizing our objective becomes NP-hard with more than two label types, but we develop fast approximation algorithms based on linear programming relaxations that have theoretical cluster quality guarantees. We demonstrate the efficacy of our algorithms and the scope of the model through problems in edge-label community detection, clustering with temporal data, and exploratory data analysis.