# A Tight Expressivity Hierarchy for GNN-Based Entity Resolution in Master Data Management

arXiv: https://arxiv.org/abs/2603.27154 · HTML: https://mlsanity.com/paper/2603.27154/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 28 Mar 2026.

## Builds on (most cited first, 15 of 15)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Provably Powerful Graph Neural Networks for Directed Multigraphs](https://mlsanity.com/paper/2306.11586/) (2023)
- [edGNN: a Simple and Powerful GNN for Directed Labeled Graphs](https://mlsanity.com/paper/1904.08745/) (2019)
- [AutoBlock: A Hands-off Blocking Framework for Entity Matching](https://mlsanity.com/paper/1912.03417/) (2019)
- [Link Prediction using Graph Neural Networks for Master Data Management](https://mlsanity.com/paper/2003.04732/) (2020)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)
- [Graph Data Management and Graph Machine Learning: Synergies and Opportunities](https://mlsanity.com/paper/2502.00529/) (2025)
- [TeMP-TraG: Edge-based Temporal Message Passing in Transaction Graphs](https://mlsanity.com/paper/2503.16901/) (2025)
- [SliceGX: Layer-wise GNN Explanation with Model-slicing](https://mlsanity.com/paper/2506.17977/) (2025)

## Abstract (arXiv)

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. Applying a message-passing neural network (MPNN) with all available extensions (reverse message passing, port numbering, ego IDs) incurs unnecessary overhead, since different entity resolution tasks have fundamentally different complexity. For a given matching criterion, what is the cheapest MPNN architecture that provably works? We answer this with a four-theorem separation theory on typed entity-attribute graphs. We introduce co-reference predicates Dupr (two same-type entities share at least r attribute values) and the ℓ-cycle predicate Cycℓ for settings with entity-entity edges. For each predicate we prove tight bounds -- constructing graph pairs provably indistinguishable by every MPNN lacking the required adaptation, and exhibiting explicit minimal-depth MPNNs that compute the predicate on all inputs. The central finding is a sharp complexity gap between detecting any shared attribute and detecting multiple shared attributes. The former is purely local, requiring only reverse message passing in two layers. The latter demands cross-attribute identity correlation -- verifying that the same entity appears at several attributes of the target -- a fundamentally non-local requirement needing ego IDs and four layers, even on acyclic bipartite graphs. A similar necessity holds for cycle detection. Together, these results yield a minimal-architecture principle: practitioners can select the cheapest sufficient adaptation set, with a guarantee that no simpler architecture works. Computational validation confirms every prediction.