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

• URL: http://arxiv.org/abs/2603.27154v1
• Date: Sat, 28 Mar 2026 06:38:03 GMT
• Title: A Tight Expressivity Hierarchy for GNN-Based Entity Resolution in Master Data Management
• Abstract summary: We prove a four-theorem separation theory on typed entity-attribute graphs.<n>For each predicate we prove tight bounds -- constructing graph pairs provably indistinguishable by every MPNN lacking the required adaptation.<n>Results yield a minimal-architecture principle: practitioners can select the cheapest sufficient adaptation set, with a guarantee that no simpler architecture works.
• Score: 2.4366811507669115
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• COMBINER: Composed Image Retrieval Guided by Attribute-based Neighbor Relations [73.40758654107724]
  We introduce a COMposed image retrieval network guided by By attrIbute-based NEighbor Relations (COMBINER)<n>Specifically, we first design an Adaptive Semantic Disentanglement module, which is capable of disentangling attribute features.<n> Secondly, we propose a Unified Prototype-based Composition module, which can construct cross-modal unified prototypes.<n>Finally, we introduce a Dual Relations Modeling module, which can mine pairwise and neighbor relations based on attribute similarity.
  arXiv  Detail & Related papers  (2026-06-03T08:43:51Z)
• BIRDNet: Mining and Encoding Boolean Implication Knowledge Graphs as Interpretable Deep Neural Networks [1.200935710020835]
  We encode a graph as the connectivity of a layered neural network, called BIRDNet.<n>Each hidden unit corresponds to one mined rule and binds only to its two features.<n>We evaluate BIRDNet on six transcriptomic and proteomic benchmarks.
  arXiv  Detail & Related papers  (2026-05-27T16:59:01Z)
• Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations [5.193718340934995]
  MEGA-GNN is a unified framework for message passing on multigraphs.<n>We show that MEGA-GNN is not only permutation equivariant but also universal given a strict total ordering on the edges.<n>Experiments show that MEGA-GNN significantly outperforms state-of-the-art solutions by up to 13% on Anti-Money Laundering datasets.
  arXiv  Detail & Related papers  (2024-11-29T20:15:18Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQ is a new formulation for scene graph generation that avoids the multi-task learning problem and the entity pair distribution. We employ a DETR-based encoder-decoder conditional queries to significantly reduce the entity label space as well. Experimental results show that TraCQ not only outperforms existing single-stage scene graph generation methods, it also beats many state-of-the-art two-stage methods on the Visual Genome dataset.
  arXiv  Detail & Related papers  (2023-06-09T06:02:01Z)
• Attribute-Consistent Knowledge Graph Representation Learning for Multi-Modal Entity Alignment [14.658282035561792]
  We propose a novel attribute-consistent knowledge graph representation learning framework for MMEA (ACK-MMEA) Our approach achieves excellent performance compared to its competitors.
  arXiv  Detail & Related papers  (2023-04-04T06:39:36Z)
• Densely Connected $G$-invariant Deep Neural Networks with Signed Permutation Representations [6.200483285433661]
  We introduce and investigate, for finite groups $G$, $G$-invariant deep neural network ($G$-DNN) architectures with ReLU activation. The preactivations of the $G$-DNNs are able to transform by emphsigned permutation representations (signed perm-reps) of $G$. We show that there are far more admissible $G$-DNN architectures than those accessible with the concatenated ReLU'' activation function from the literature.
  arXiv  Detail & Related papers  (2023-03-08T14:35:03Z)
• AutoAC: Towards Automated Attribute Completion for Heterogeneous Graph Neural Network [18.47866953955945]
  We propose a differentiable attribute completion framework called AutoAC for automated completion operation search in heterogeneous GNNs. We show that AutoAC outperforms the SOTA handcrafted heterogeneous GNNs and the existing attribute completion method.
  arXiv  Detail & Related papers  (2023-01-08T14:38:32Z)
• Trigger-GNN: A Trigger-Based Graph Neural Network for Nested Named Entity Recognition [5.9049664765234295]
  We propose a trigger-based graph neural network (Trigger-GNN) to leverage the nested NER. It obtains the complementary annotation embeddings through entity trigger encoding and semantic matching. It helps the model to learn and generalize more efficiently and cost-effectively.
  arXiv  Detail & Related papers  (2022-04-12T04:15:39Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Modeling Heterogeneous Hierarchies with Relation-specific Hyperbolic Cones [64.75766944882389]
  We present ConE (Cone Embedding), a KG embedding model that is able to simultaneously model multiple hierarchical as well as non-hierarchical relations in a knowledge graph. In particular, ConE uses cone containment constraints in different subspaces of the hyperbolic embedding space to capture multiple heterogeneous hierarchies. Our approach yields new state-of-the-art Hits@1 of 45.3% on WN18RR and 16.1% on DDB14 (0.231 MRR)
  arXiv  Detail & Related papers  (2021-10-28T07:16:08Z)
• Meta-Aggregator: Learning to Aggregate for 1-bit Graph Neural Networks [127.32203532517953]
  We develop a vanilla 1-bit framework that binarizes both the GNN parameters and the graph features. Despite the lightweight architecture, we observed that this vanilla framework suffered from insufficient discriminative power in distinguishing graph topologies. This discovery motivates us to devise meta aggregators to improve the expressive power of vanilla binarized GNNs.
  arXiv  Detail & Related papers  (2021-09-27T08:50:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.