マスターデータ管理におけるGNNベースのエンティティ解決のための、タイトな表現力階層
arXiv cs.LG / 2026/3/31
💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research
要点
- 本論文は、エンティティ–属性関係を型付き二部グラフ（必要に応じてエンティティ–エンティティも）としてモデル化し、MPNNで処理することで、マスターデータ管理におけるエンティティ解決を研究する。
- 2つの論理述語（共有属性値を少なくともr個検出するためのDup_r、ℓ-サイクルを検出するためのCyc_ell）を用いて、最も安価であることが証明できるGNNアーキテクチャを要求するための、4つの定理による分離（separation）フレームワークを構築する。
- 主結果は、表現力と計算量の間における「タイトな（tight）ギャップ」である。すなわち、任意の共有属性の検出は局所的であり、逆向きメッセージパッシングを用いた最小の2層MPNNで実現できる。一方で、複数の共有属性の検出には、属性間の相関という非局所性が必要となる。
- Dup_r（r>1）および関連するサイクル検出について、本論文は、たとえ非サイクルの二部グラフであっても、エゴIDと4層の深さが本質的に必要であり、より単純なMPNN変種では、すべての入力に対してこれらの述語を計算できないことを示す。
- さらに、最小深度の構成的（constructive）MPNNアーキテクチャも提示し、計算による検証を理論的予測と一致させることで、実務者向けの「最小アーキテクチャ原理」を可能にする。
