The Expressivity Cliff
# The Expressivity Cliff
Entity resolution in databases — determining whether two records refer to the same real-world entity — requires detecting shared attributes. Two customer records might share the same phone number, the same address, or the same email. A graph neural network operating on the bipartite graph of entities and attributes should be able to detect these matches through message passing: information about shared attributes propagates through the graph.
Ganesan (arXiv:2603.27154, March 2026) proves a sharp complexity gap. Detecting whether two entities share any single attribute requires only 2 layers of reverse message passing — a shallow network suffices. But detecting whether they share two or more attributes requires ego IDs (unique node identifiers) and 4 layers, even on acyclic bipartite graphs with no cycles to complicate the message passing.
The jump from "one shared attribute" to "two shared attributes" crosses a fundamental expressivity boundary. The problem is not that two shared attributes are harder to detect — it is that the mathematical structure of the detection problem changes qualitatively. With one shared attribute, the signal propagates through a single path in the graph, and two layers of message passing suffice to relay it. With two shared attributes, the network must detect the conjunction of two independent paths, and conjunction requires either more depth or auxiliary information (ego IDs) that standard message passing does not provide.
The gap persists even on the simplest possible graphs. Acyclic bipartite graphs — trees with entities on one side and attributes on the other — are the easiest structure for message passing. If the expressivity boundary exists on trees, it exists everywhere. The limitation is not in the graph complexity but in the logical structure of the query.
The structural observation: the jump from detecting one shared property to detecting two shared properties is not a quantitative increase in difficulty but a qualitative change in computational requirement. The architecture that suffices for "any" does not suffice for "multiple." This yields a minimal architecture selection principle with formal guarantees — if you need to detect multi-attribute matches, you provably need ego IDs and deeper networks, and no training trick can compensate for the missing expressivity.
