Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges

Edge-colored clustering (ECC) is an optimization framework for clustering datasets characterized by categorical relationships among data points. The problem is formally encoded as an edge-colored hypergraph (Figure 1), where each edge represents an interaction between data objects (the nodes) and the color of the edge indicates the type or category of that interaction. The goal is to assign colors to nodes in such a way that edges of a color tend to include nodes of that color, by minimizing or maximizing some objective function relating edge colors and node colors. ECC algorithms have been applied to various clustering tasks where cluster labels naturally match with interaction types. For example, if nodes are researchers, edges are author lists for publications, and colors indicate publication field (computer science, biology, etc.), then ECC provides a framework for inferring researchers' fields based on publications. ECC has also been used for temporal hypergraph clustering [Amburg et al., 2020], where edge colors encode time windows in which interactions occur. ECC then clusters nodes into time windows in which they are especially active. Variants of ECC have also been used for team formation [Amburg et al., 2022], in which case nodes are people, edges represent team tasks, and colors indicate task type. In this setting, ECC corresponds to assigning tasks based on prior team experiences.