論文の概要: A Tight Expressivity Hierarchy for GNN-Based Entity Resolution in Master Data Management

• arxiv url: http://arxiv.org/abs/2603.27154v1
• Date: Sat, 28 Mar 2026 06:38:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-31 23:18:44.817508
• Title: A Tight Expressivity Hierarchy for GNN-Based Entity Resolution in Master Data Management
• Title（参考訳）: マスターデータ管理におけるGNNに基づくエンティティ解決のための高次表現性階層
• Authors: Ashwin Ganesan,
• Abstract要約: 型付き実体属性グラフ上での4つの理論分離理論を証明する。 各述語について、我々は厳密な境界を証明し、必要な適応を欠く全てのMPNNによって証明不可能なグラフペアを構築する。 実践者は、より単純なアーキテクチャが機能しないことを保証するため、最も安価な適応セットを選択できる。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: エンティティの解決 -- 同じ現実世界のエンティティを参照するデータベースレコードを識別する -- は、エンティティノードを属性値に接続する二部グラフを自然にモデル化する。 メッセージパッシングニューラルネットワーク(MPNN)にすべての利用可能な拡張(リバースメッセージパッシング、ポート番号、エゴID)を適用すると、さまざまなエンティティ解決タスクが根本的に異なる複雑さを持つため、不要なオーバーヘッドが発生する。 マッチング基準について言えば、確実に機能する最も安価なMPNNアーキテクチャは何ですか? これを、型付き実体属性グラフ上の4つの理論分離理論で解する。 我々は、エンティティエンタリティエッジの設定に対して、共参照述語 $\mathrm{Dup}_r$ (2つの同型エンティティが少なくとも$r$属性値を共有する) と $\ell$-cycle述語 $\mathrm{Cyc}_\ell$ を導入する。 各述語について厳密な境界を証明し、必要な適応を欠いた全てのMPNNでグラフペアを確実に区別できないようにし、全ての入力で述語を計算するための明示的な最小限のMPNNを示す。 中心的な発見は、共有属性を検出したり、複数の共有属性を検出したりするという、非常に複雑なギャップである。 前者は純粋にローカルであり、2つの層でメッセージの逆渡ししか必要としない。 後者はクロス属性のID相関を要求する -- 同じエンティティがターゲットのいくつかの属性に現れることを検証する -- 基本的には、非循環的な二部グラフでさえ、エゴIDと4つのレイヤを必要とする非局所的な要件である。 同様にサイクル検出も必要である。 実践者は、より単純なアーキテクチャが機能しないことを保証するため、最も安価な適応セットを選択できる。 計算検証は全ての予測を確認する。

関連論文リスト

• Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations [5.193718340934995]
  MEGA-GNNは、マルチグラフ上のメッセージパッシングのための統一されたフレームワークである。 我々は, MEGA-GNN が置換同変であるだけでなく,エッジ上で厳密な全順序付けを与えられることも示す。 実験の結果、MEGA-GNNはアンチ・モニー・ロンダリングのデータセットで最先端のソリューションを最大13%上回っていることがわかった。
  論文  参考訳（メタデータ） (2024-11-29T20:15:18Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQは、マルチタスク学習問題とエンティティペアの分布を回避する、シーングラフ生成の新しい定式化である。 我々は,DETRをベースとしたエンコーダ-デコーダ条件付きクエリを用いて,エンティティラベル空間を大幅に削減する。 実験結果から、TraCQは既存のシングルステージシーングラフ生成法よりも優れており、Visual Genomeデータセットの最先端の2段階メソッドを多く上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-06-09T06:02:01Z)
• Attribute-Consistent Knowledge Graph Representation Learning for Multi-Modal Entity Alignment [14.658282035561792]
  MMEA(ACK-MMEA)のための属性一貫性のある知識グラフ表現学習フレームワークを提案する。 当社のアプローチは、競合他社と比較して優れたパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2023-04-04T06:39:36Z)
• Densely Connected $G$-invariant Deep Neural Networks with Signed Permutation Representations [6.200483285433661]
  有限群$G$,$G$-不変ディープニューラルネットワーク(G$-DNN)アーキテクチャをReLUアクティベーション付きで導入・検討する。 G$-DNNのプリアクティベーションは、Emphsigned permutation representations (signed perm-reps) of $G$で変換できる。 文献からReLUのアクティベーション関数にアクセスできるものよりも、より許容可能な$G$-DNNアーキテクチャが存在することを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:35:03Z)
• AutoAC: Towards Automated Attribute Completion for Heterogeneous Graph Neural Network [18.47866953955945]
  異種GNNにおける自動完了操作探索のための AutoAC という異種属性補完フレームワークを提案する。 我々は,AutoACがSOTAの手作りヘテロジニアスGNNと既存の属性補完法より優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-08T14:38:32Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  本モデルでは,既存のKG補完アルゴリズムよりも複雑な推論パターンを必要とする問合せに対して,より効果的に答えることを示す。 提案モデルは、KBQAベンチマークの最先端モデルよりも優れているか、競合的に動作する。
  論文  参考訳（メタデータ） (2022-02-22T01:34:35Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)
• Modeling Heterogeneous Hierarchies with Relation-specific Hyperbolic Cones [64.75766944882389]
  知識グラフにおける複数の階層的および非階層的関係を同時にモデル化できるKG埋め込みモデルであるConE(Cone Embedding)を提案する。 特に、ConEは双曲埋め込み空間の異なる部分空間における円錐包含制約を用いて、複数の異種階層をキャプチャする。 我々のアプローチでは、WN18RRで45.3%、DDB14で16.1%の新しい最先端hits@1が得られる(0.231 MRR)。
  論文  参考訳（メタデータ） (2021-10-28T07:16:08Z)
• Meta-Aggregator: Learning to Aggregate for 1-bit Graph Neural Networks [127.32203532517953]
  我々は,GNNパラメータとグラフ特徴をバイナライズするバニラ1ビットフレームワークを開発した。 軽量なアーキテクチャにもかかわらず、我々はこのバニラフレームワークがグラフトポロジを区別するのに十分な差別力に悩まされていることを観察した。 この発見は、バニラ二項化GNNの表現力を向上させるためにメタアグリゲータを考案する動機となる。
  論文  参考訳（メタデータ） (2021-09-27T08:50:37Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。