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

Jul 28, 2026

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

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.

Kaushik Pavani, Ganga Aluri, Pravin Jadhav +2

Walmart

Entity Resolution

Ask PDF

May 25, 2026

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

Dirty entity resolution (ER), which identifies records referring to the same real-world entity from a single, messy dataset, is a fundamental task in data management and mining. However, the dominant blocking-matching-clustering paradigm for ER suffers from critical flaws. Its cascaded, decoupled workflow essentially produces a static, sparse graph plagued by missing edges (due to blocking failures) and noisy links (due to matching errors), causing error propagation and yielding suboptimal clusters, particularly when rigid transitivity is imposed in the clustering. We contend that matching and clustering are fundamentally synergistic, both optimizing for the construction of an ideal entity graph. Building upon this insight, we propose Alper, a unified framework that integrates these steps into an iterative probabilistic label propagation process over a global, evolving graph. Unlike disjoint blocking, Alper refines the graph structure and labels dynamically by adaptively integrating "weak but cheap" signals from graph propagation with "strong but expensive" LLM-based pairwise queries. For higher cost-effectiveness, we formulate the signal selection as a constrained optimization problem maximizing cumulative marginal gain under a query budget, solved via our greedy algorithm with provable theoretical guarantees. Our extensive experiments over eight benchmark datasets demonstrate that Alper is consistently superior to state-of-the-art cascaded pipelines.

Hongtao Wang, Renchi Yang, Haoran Zheng +1

Hong Kong Baptist University · Hong Kong, China · Zhejiang University +1

Graph Structure Learning Entity Resolution Active Learning

Ask PDF

Jun 23, 2026

Entity Resolution via Batched Oracle Queries

We consider an oracle that processes a limited batch of records at a time and clusters those that refer to the same real-world entity. We study how to interrogate such an oracle to resolve entities in a dataset whose size is far larger than a single batch, and where no batch is guaranteed to contain all records of any given entity. We aim at a pay-as-you-go approach, to have full control over the costs (the number of oracle consults), while achieving the highest possible recall at every step. We formally cast this problem as batched entity resolution, prove that selecting optimal batches is NP-hard, and provide an optimal solution under a natural condition on entity sizes. Finally, we evaluate our approach on six datasets and show its superiority over state-of-the-art baselines.

Lorenzo Balzotti, Donatella Firmani, Luca Gagliardelli +1

Sapienza University of Rome, Rome, Italy · Universit`a eCampus, Italy · University of Modena and Reggio Emilia, Modena, Italy

Entity Resolution

Ask PDF

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