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

Ashwin Ganesan

cs.LGMar 28, 2026

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

Authors: Ashwin Ganesan

Organizations: Centre for Cybersecurity, Trust and Reliability (CyStar), Department of Computer Science and Engineering, Indian Institute of Technology, Madras, Tamilnadu, India.

Abstract

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 $\mathrm{Dup}_r$ (two same-type entities share at least $r$ attribute values) and the $\ell$ -cycle predicate $\mathrm{Cyc}_\ell$ 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.

Figures & tables

Panel of Figure 1 — Figure 1: A typed entity-attribute graph. Entities $u$ and $v$ share a common attribute node [email protected] via edge of type hasEmail .

Panel of Figure 2 — Figure 2: Separation graphs for the necessity proof of Theorem 3 .

Panel of Figure 3 — Figure 3: Separation graphs for the necessity proof of Theorem 5 .

Panel of Figure 4 — Figure 4: The simple typed entity-attribute graphs $G_{1}$ (left) and $G_{2}$ (right) from Example 7 .

Panel of Figure 5 — Figure 5: A port numbering for the simple typed entity-attribute graphs $G_{1}$ and $G_{2}$ from Example 7 . Red numbers near the source of an edge give $p_{\mathrm{out}}$ ; blue numbers near the destination of an edge give $p_{\mathrm{in}}$ . Both port numberings are valid: each entity assigns distinct outgoing ports $\{1,2\}$ to its two edges, and each attribute receives distinct incoming ports $\{1,2\}$ from its two predecessors. Under these port numberings, every MPNN without ego IDs assigns $u$ the identical embedding in both graphs.

Panel of Figure 6 — Figure 6: Port numbering for the general $K_{2,r}$ case ( $r\geq 2$ ), generalizing Figure 5 . Left ( $G_{1}$ ): two disjoint copies of $K_{2,r}$ ; the top copy has entities $u$ (class-1) and $v$ (class-2) sharing all $r$ typed attributes $a_{1},\ldots,a_{r}$ , giving $\mathrm{Dup}_{r}(u)=1$ . Right ( $G_{2}$ ): the four attribute boxes partition $\{1,\ldots,r\}=S_{1}\dot{\cup}S_{2}$ (with $S_{1},S_{2}\neq\emptyset$ ); entity $u$ ’s $r$ attributes are split across $v_{1}$ (covering $S_{1}$ -indices) and $v_{2}$ (covering $S_{2}$ -indices), so no single entity shares $r$ typed neighbors with $u$ , giving $\mathrm{Dup}_{r}(u)=0$ . Each bundled arrow represents $|S_{i}|$ parallel edges, one per index $j$ in the relevant set. Red near the tail gives $p_{\mathrm{out}}$ (equal to $j$ for the $\tau_{j}$ -edge); blue near the head gives $p_{\mathrm{in}}$ . Class-1 entities ( $u$ , $w$ in $G_{1}$ ; $u$ , $v_{3}$ in $G_{2}$ ) receive $p_{\mathrm{in}}=1$ at every incident attribute box; class-2 entities ( $v$ , $x$ ; $v_{1}$ , $v_{2}$ ) receive $p_{\mathrm{in}}=2$ . The computation trees rooted at $u$ are therefore isomorphic in $G_{1}$ and $G_{2}$ , making $u$ indistinguishable to any MPNN without ego IDs.

Layer	Direction	Message content	Node computes and stores
0	—	—	Entity $v$ : $(\tau_{V}(v),\mathrm{ego}_{u}(v))$ . Attribute $a$ : $\tau_{V}(a)$ .
1	Ent $\to$ Att	$(\tau_{V}(v),\mathrm{ego}_{u}(v),\tau)$	Attribute $a$ : $\mathrm{EgoTypes}(a)\subseteq\mathcal{T}_{E}$
2	Att $\to$ Ent	$(h^{(1)}(a),\tau)$	Entity $v$ : $\bigl(\tau_{V}(v),\,\mathrm{ego}_{u}(v),\,\mathrm{ov}(v)\bigr)$
3	Ent $\to$ Att	$(\tau_{V}(v),\mathrm{ego}_{u}(v),\mathrm{ov}(v),\tau)$	Attribute $a$ : $\mathrm{maxOv}(a)\in\mathbb{Z}_{\geq 0}$
4	Att $\to$ Ent	$(\mathrm{maxOv}(a),\tau)$	Ego $u$ : $\hat{y}(u)=\mathbf{1}\!\bigl[\max_{a\in N_{\mathrm{out}}(u)}\mathrm{maxOv}(a)\geq r\bigr]$

Table 1: Summary of the 4-layer MPNN construction for computing

\mathrm{Dup}_{r}(u)

(proof of sufficiency, Theorem 8 ). Layers alternate between forward passes (entity

\to

attribute) and reverse passes (attribute

\to

entity). Each message is a tuple of bounded scalars; the ego indicator

\mathrm{ego}_{u}(v)=\mathbf{1}[v=u]

is set at Layer 0 and carried forward in every subsequent embedding. The quantity

\mathrm{ov}(v)=|N_{\mathrm{typed}}(u)\cap N_{\mathrm{typed}}(v)|

is the overlap count established at Layer 2 (Lemma 9 );

\mathrm{maxOv}(a)

is the maximum overlap count among non-ego same-type entities incident to

a

, computed at Layer 3.

Thm	Architecture (insufficient)	$\max_{i}\lVert h_{G_{1}}(u)-h_{G_{2}}(u)\rVert_{2}$
3	Vanilla MPNN (no reverse MP)	$0.00$
5	$+\,$ Reverse MP (no ports)	$0.00$
8	$+\,$ Reverse MP $+$ Full Ports (no ego)	$0.00$
12	$+\,$ Reverse MP $+$ Full Ports (no ego)	$0.00$

Table 2: Necessity validation. The

\ell_{2}

distance between the target node’s embedding in

G_{1}

and

G_{2}

is exactly zero for all

100

random weight initialisations at every depth tested. Tested depths:

K\in\{2,4\}

for Theorems 3 and 5 ;

K\in\{2,4,6\}

for Theorem 8 ;

K\in\{3,6\}

for Theorem 12 . The result confirms the structural indistinguishability established in the necessity proofs.

Thm	Architecture (sufficient)	Params	$\hat{y}(u)$ on $G_{1}$	$\hat{y}(u)$ on $G_{2}$
3	$+\,$ Reverse MP (2 layers)	—	$1=\mathrm{Dup}_{G_{1}}(u)$	$0=\mathrm{Dup}_{G_{2}}(u)$
5	$+\,$ RevMP $+$ InPorts (2 layers)	—	$1=\mathrm{Dup}_{G_{1}}(u)$	$0=\mathrm{Dup}_{G_{2}}(u)$
8	$+\,$ RevMP $+$ Ego (4 layers)	$r=2$	$1=\mathrm{Dup}_{2,G_{1}}(u)$	$0=\mathrm{Dup}_{2,G_{2}}(u)$
		$r=3$	$1=\mathrm{Dup}_{3,G_{1}}(u)$	$0=\mathrm{Dup}_{3,G_{2}}(u)$
		$r=4$	$1=\mathrm{Dup}_{4,G_{1}}(u)$	$0=\mathrm{Dup}_{4,G_{2}}(u)$
12	$+\,$ Ego, fwd-only ( $\ell$ layers)	$\ell=3$	$1=\mathrm{Cyc}_{3,G_{1}}(u)$	$0=\mathrm{Cyc}_{3,G_{2}}(u)$

Table 3: Sufficiency validation. Each row implements the exact MPNN construction from the corresponding sufficiency proof and reports its output for the designated target node on the canonical separation graphs. No training or random initialisation is involved; the construction is deterministic.

Entity resolution task	Graph class	Minimal sufficient adaptations	Provably unnecessary	Depth	Thm
$K_{2,1}$ detection	Simple entity-attribute	Reverse message passing	Port numbering, ego IDs	2	3
$K_{2,1}$ detection	Multigraph entity-attribute	Reverse message passing, incoming ports	Outgoing ports, ego IDs	2	5
$K_{2,r}$ detection ( $r\geq 2$ )	Simple entity-attribute	Reverse message passing, ego IDs	Port numbering	4	8
$K_{2,r}$ detection ( $r\geq 2$ )	Multigraph entity-attribute	Reverse message passing, incoming ports, ego IDs	Outgoing ports	4	5 , 8
$\ell$ -cycle detection	Typed directed	Ego IDs †	Reverse message passing, port numbering †	$\ell$	12

Table 4: Minimal architecture principle for entity resolution. Each row gives the cheapest sufficient MPNN adaptation set and the provably optimal depth for the corresponding entity resolution task and graph class, together with the adaptations that are provably unnecessary. Every necessity claim holds for MPNNs of arbitrary depth and width; every sufficiency claim is constructive, with an explicit MPNN of the stated depth. The stated depths are optimal: for each row, we prove that no MPNN of smaller depth can compute the target predicate, even with all three adaptations. † On the separation pair

G_{1}=2C_{\ell}

G_{2}=C_{2\ell}

only; universal

\mathrm{Cyc}_{\ell}

computation on all typed directed multigraphs requires the full triple of adaptations [ 4 , Corollary 4.4.1] .

Entity Resolution

Entity resolution links records that refer to the same real-world entity across datasets despite differences in names, attributes, formats, and languages.

See all 39 papers

Entity Resolution in Practice: Lessons from a Self-Serve Pipeline
Jul 28, 2026Kaushik Pavani, Ganga Aluri, Pravin Jadhav +2Entity Resolution
Walmart
Adaptive Graph Refinement and Label Propagation with LLMs for Cost-Effective Entity Resolution
May 25, 2026Hongtao Wang, Renchi Yang, Haoran Zheng +1Graph Structure Learning Entity Resolution
Hong Kong Baptist University · Hong Kong, China · Zhejiang University +1
Entity Resolution via Batched Oracle Queries
Jun 23, 2026Lorenzo Balzotti, Donatella Firmani, Luca Gagliardelli +1Entity Resolution
Sapienza University of Rome, Rome, Italy · Universit`a eCampus, Italy · University of Modena and Reggio Emilia, Modena, Italy

Jul 28, 2026J/K move · Enter open · S save

Entity Resolution in Practice: Lessons from a Self-Serve Pipeline

Kaushik Pavani, Ganga Aluri, Pravin Jadhav, Neeraj Prasad+1

Walmart

Entity Resolution

Open paper AskPDF arXiv

We built and evaluated a self-serve entity resolution (ER) system on six benchmarks spanning 864 to 5M records, and three lessons emerged that are absent from existing ER literature. (1) No single matching algorithm wins everywhere - a self-serve pipeline cannot predict its next dataset, so we recommend training several algorithm families per dataset and letting an automatic bake-off pick the winner. (2) Precision and recall need separate fixes, not a shared threshold - precision needs hard rule-based vetoes, recall needs more diverse candidate retrieval. (3) One false-positive link can silently merge unrelated entities - assuming "A matches B" and "B matches C" implies "A matches C" lets a single bad link chain hundreds of records together, so every cross-group merge must be actively re-verified. We hope these lessons save practitioners the months of dead-end experiments that led us to them.

Abstract

Entity Resolution

Explore similar work

Entity Resolution in Practice: Lessons from a Self-Serve Pipeline

Adaptive Graph Refinement and Label Propagation with LLMs for Cost-Effective Entity Resolution

Entity Resolution via Batched Oracle Queries