We introduce a new family of abstractions based on a data
structure that we call \emph{labeled union-find}, an extension of
the classic efficient union-find data structure where edges carry
labels. These labels have a composition operation that obey the group axioms.
Like union-find, the labeled
version can efficiently compute the transitive closure of a
relation, but it is not limited to equivalence relations; it
can represent any injective transformation between equivalence
classes, which includes two-variables per equality (TVPE)
constraints of the form $y = a\times x + b$. Using abstract
interpretation theory, we study the properties deriving from the use of
abstract relations as labels, and the combination of labeled
union-find with other representations of constraints, allowing both
improvements in precision and simplification of existing constraints.
Due to its efficiency, the labeled union-find abstractions could
find many uses; we use it in two use cases, program analysis based
on abstract interpretation and constraint solving for SMT, with
encouraging preliminary results.