In this work-in-progress paper, we present labeled union-find, an extension of the union-find data structure where edges are annotated with labels that form a group algebraic structure. This structure allows to very efficiently represent the transitive closure of many useful binary relations, such as two-variables per equality (TVPE) constraints of the form y = a*x + b. We characterize the properties of labeled union-find when used to represent binary relations between variables. More specifically, we study the use of this domain in a static analysis; either to represent binary relations, or as a reduced product with non-relational abstract domains with constraint propagation; as well as the design of efficient algorithms for the join of labeled union-find structures. We believe that this structure could be used as a low-cost relational domain or decision procedure, and that it could make other relational domains more efficient by removing the need to track some variables.