Clustering in graphs and hypergraphs with categorical edge labels
Authors:
Top Cited Papers
Open Access
- 20 April 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 706-717
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
This publication has 52 references indexed in Scilit:
- 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
- Community detection in graphsPhysics Reports, 2010
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- What energy functions can be minimized via graph cuts?IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Multiway cuts in node weighted graphsJournal of Algorithms, 2004
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Fast approximate energy minimization via graph cutsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Clustering categorical data: an approach based on dynamical systemsThe VLDB Journal, 2000