Entity resolution — identifying database records that refer to the same real-world entity — is naturally modelled on bipartite graphs connecting entity nodes to their attribute values. A common approach is to apply a message-passing neural network (MPNN) enriched with all available architectural extensions (reverse message passing, port numbering, ego IDs), but this results in unnecessary computational overhead, since different entity resolution tasks have fundamentally different complexity. A natural question is therefore: for a given matching criterion, what is the cheapest MPNN architecture that provably works? In this work, we answer this question with a four-theorem separation theory on typed entity-attribute graphs. We introduce a family of co-reference predicates, Dupᵣ, capturing the evidence pattern "two same-type entities share at least r attribute values, " together with the ℓ-cycle participation predicate Cyc_ℓ for settings with entity–entity edges. For the co-reference predicates, we prove tight lower and upper bounds — constructing graph pairs that are provably indistinguishable by every MPNN lacking the required adaptation, and exhibiting explicit, minimal-depth MPNNs that compute the predicate correctly on all inputs. For cycle detection, we prove the necessity of ego IDs and demonstrate their sufficiency on the canonical separation instances. The central finding is a sharp complexity gap between detecting any shared attribute and detecting multiple shared attributes. The former is a purely local computation: each attribute can independently check whether two same-type entities point to it, requiring only reverse message passing in two layers. The latter demands what we call cross-attribute identity correlation — verifying that the same entity appears at several attributes of the target — a fundamentally non-local requirement that necessitates ego IDs and four layers, even on the simplest class of acyclic bipartite graphs. A similar necessity holds for cycle detection. Taken together, these results yield a minimal-architecture principle: practitioners can select the cheapest adaptation set that provably suffices for their specific matching criterion, with a guarantee that no simpler architecture works. Computational validation confirms every theoretical prediction.
Ashwin Ganesan (Sat,) studied this question.