Abstract

In 1967, Lovász proved that two graphs G and H are isomorphic if, and only if, they are homomorphism indistinguishable over the the family of all graphs, i.e. for all graphs F the number of homomorphisms from F to G is equal to the number of homomorphisms from F to H. In recent years, many natural relaxations of graph isomorphism from fields as diverse as quantum information theory, algebraic graph theory, convex optimisation, and category theory have been characterised as homomorphism indistinguishability relations over restricted graph classes. Furthermore, homomorphism indistinguishability has proven useful for analysing graph learning architectures as demonstrated by Zhang, Gai, Du, Ye, He, & Wang (2024) and Gai, Du, Zhang, Maron, & Wang (2025).

Abstracting from the wealth of these results, we set out to develop a theory of homomorphism indistinguishability that provides insights into the descriptive and computational complexity of graph isomorphism relaxations. That is, for a graph class 𝓕, we ask

- what is the distinguishing power of homomorphism counts from graphs F ∊ 𝓕 and
- what is the complexity of deciding homomorphism indistinguishability over 𝓕?

Video Recording