Clustering in graphs and hypergraphs with categorical edge labels
Preprint
Abstract
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.Keywords
All Related Versions
- Version 1, 2019-10-22, ArXiv
- Version 2, 2020-02-17, ArXiv
- Published version: , 706.
This publication has 20 references indexed in Scilit:
- Simplicial closure and higher-order link predictionProceedings of the National Academy of Sciences, 2018
- Clustering attributed graphs: Models, measures and methodsNetwork Science, 2015
- Cognitive relevance of the community structure of the human brain functional coactivation networkProceedings of the National Academy of Sciences, 2013
- Consensus clustering in complex networksScientific Reports, 2012
- Flavor network and the principles of food pairingScientific Reports, 2011
- Networks, Crowds, and Markets2010
- Patterns and dynamics of users' behavior and interaction: Network analysis of an online communityJournal of the American Society for Information Science and Technology, 2009
- Multiway cuts in node weighted graphsJournal of Algorithms, 2004
- An Improved Approximation Algorithm for MULTIWAY CUTJournal of Computer and System Sciences, 2000
- Clustering categorical data: an approach based on dynamical systemsThe VLDB Journal, 2000