When two knowledge graphs describe the same people, books, or films, a common way to connect them is a link key. A link key is a rule such as "if a record in dataset A and a record in dataset B share a title value and share an author value, declare them the same entity." A line of work grounded in formal concept analysis (a lattice-based method that groups objects by the attributes they jointly share) can enumerate every candidate link key from the data and organise the candidates into a lattice. That same work shows that the best interlinking comes from taking the union of several keys. All of these methods treat each property value as simply present or absent. Real values are not like that: they come from extractors with known error rates, from sources of differing reliability, or from earlier reasoning steps. As a result, the methods cannot say how likely a produced link is, or which sources it depends on. They also choose which keys to combine without accounting for the fact that two keys built on the same unreliable property fail together.
We propose to treat a disjunction of link keys exactly as a database treats a union of conjunctive queries. Under that view, every link it produces carries a provenance polynomial: an algebraic record of which value matches, joined by AND and OR, support the link. We compute this record once on top of the existing pattern-structure lattice. We then evaluate it under any semiring, meaning any algebra that replaces AND and OR with an operation suited to the question, such as probability, source trust, clearance level, or number of independent supporting keys. Finally, we use the exact link probabilities to choose which keys enter the disjunction. The claim we will test is narrow. On uncertain data, selecting and scoring disjunctions with exact, correlation-aware link probabilities should beat both crisp lattice selection and post-hoc annotation of crisply chosen keys. A single annotated lattice should also stand in for re-mining the lattice in every sampled possible world.
Core Claim
The link-key lattice papers handle combinations of keys only as set unions. Several Link Keys are Better than One proves that conjunctions of keys add no links while disjunctions raise recall, and it searches antichains of the lattice with top-k and expand-best heuristics. Linkex supplies the pattern structures. These describe each instance pair by which aligned property pairs agree, with In meaning "at least one shared value" and Eq meaning "identical value sets." Semiring provenance, as built into ProvSQL, already knows how to represent a union of conjunctions compactly as a circuit. It also knows how to evaluate that circuit exactly by compiling it into a form where probability can be computed in time linear in its size (Database Theory in Action).
The connection is precise. Attach a token $x_{a,p,v}$ to each triple stating that instance $a$ has value $v$ for property $p$, and a token $y_{b,q,v}$ on the other side. For a disjunction $D$ of link keys, each key $k$ being a set of aligned property pairs $(p,q)$ with In conditions, the provenance of the candidate link $(a,b)$ is
$$\pi_D(a,b) = \bigoplus_{k \in D} \; \bigotimes_{(p,q) \in k} \; \bigoplus_{v \in p(a) \cap q(b)} x_{a,p,v} \otimes y_{b,q,v},$$
where $\oplus$ and $\otimes$ are the semiring's OR-like and AND-like operations and $p(a)$ is the set of values of $p$ on $a$.
The foundational result we will prove is straightforward but important. For In-only keys, the conditions are monotone in the presence of values. So in every possible world, the link set of $D$ equals the set of pairs whose $\pi_D$ evaluates to true under the Boolean semiring. Two consequences follow. First, the crisp lattice mined once over the union of all possible values contains every candidate key that could arise in any world, so there is no need to re-mine per world. Second, link probabilities computed from $\pi_D$ are exact rather than estimated. Eq conditions are non-monotone. They require negation gates of the kind ProvSQL already supports, and we treat them as a second, harder case.
The polynomial makes visible something the set-union view hides. Two keys that share a property pair share tokens, so their failures are correlated. A disjunction of $\{title, author\}$ and $\{title, year\}$ is far less robust to a noisy title field than a naive "noisy-OR of keys" would suggest.
Research Program
The first step is building the annotated lattice. We keep the Linkex pattern-structure lattice unchanged and attach to each concept extent a pointer-based provenance circuit per instance pair, following ProvSQL's design of shared circuit gates rather than expanded formulas. Because link keys are evaluated over a fixed, materialised lattice, there is no recursion at this stage. This sidesteps the divergence issues identified for recursive rules in Revisiting Semiring Provenance for Datalog. We leave the interdependent keys produced by relational concept analysis, where identity of persons depends on identity of places, to a later phase. That phase will use the polynomial-size circuits for minimal-depth-tree semantics from that Datalog paper.
The second step is evaluating links under different semirings. The same circuit is evaluated under several algebras. In the probability semiring, we compile the Boolean circuit with an off-the-shelf knowledge compiler as ProvSQL does. The min-max semiring gives the weakest source each link depends on. A counting semiring gives the number of independent key derivations. Shapley-value attribution over the circuit says which properties or sources carry each link, following the explanation methods surveyed in Representation, Provenance, and Explanations.
The third step is selecting disjunctions. We replace the κ-based or top-k choice of keys with greedy expand-best search, scoring each candidate disjunction by the expected F-measure under the exact link probabilities. Each greedy step adds the key whose inclusion most increases expected F-measure. Because expected true positives are sums of exact marginals, correlated keys are penalised automatically. The cost of this step is compiling incremental circuits, which we will measure rather than assume to be cheap.
The fourth step is a negative-result analysis. We will characterise the regime where all of this is unnecessary. When keys in the chosen disjunction share no property pairs and tokens are independent, exact probability reduces to a closed-form noisy-OR. We predict that the gain over simple scoring grows with the overlap of property pairs among selected keys. We will report the result even if that prediction fails.
Baselines
The naive reference point is crisp Linkex followed by top-k disjunction selection, as in Several Link Keys are Better than One. It ignores annotations entirely and treats every value as certain. It runs on the same union-of-values context. Beating it means higher F-measure against reference links once noise is injected, and no worse F-measure at zero noise.
The strongest selection method in the file is partition-based selection of non-redundant keys. A Study of the Discovery and Redundancy of Link Keys reports that on DB-Yago "Actor" the best link key candidate reached an F-measure of 0.95, compared with 0.34 for coverage and discriminability measures. On clean DB-Yago we do not expect to beat 0.95. The fair test is to reproduce that method on our noise-injected versions with identical inputs. Beating it means a statistically reliable F-measure gain across noise levels on at least most of the nine DB-Yago tasks. We also run LKCLUST with its discriminability threshold of 0.9, plus a small sweep of thresholds tuned on the same validation links our method uses. That paper itself reports sudden recall drops at the fixed setting.
The two-stage baseline is the reviewer's most natural proposal. It runs crisp selection, then translates the chosen keys to SQL and lets ProvSQL compute exact link probabilities, thresholding links on a validation split. This baseline has full provenance, but provenance plays no role in choosing which keys to use. It isolates our key ingredient, provenance-informed selection.
The ablation keeps our selection loop but replaces exact compiled probabilities with an independence approximation that treats each key as an independent event (noisy-OR). This isolates whether exactness under shared tokens matters. All methods get the same lattice, the same validation links for any tuning, and the same wall-clock budget per task.
Why not just…?
Why not just mine keys crisply and annotate the resulting links afterwards with ProvSQL? This is the real threat. If the keys that are best on crisp data are also best on noisy data, the two-stage pipeline matches us at lower cost. It is weaker exactly when noise selectively corrupts some properties. Then a crisply excellent key built on a corrupted property should be dropped in favour of a lower-coverage key on reliable properties, and only provenance-aware selection makes that swap. Our experiment that corrupts properties unequally decides this. If the two pipelines are within noise of each other there, the selection contribution fails and the paper reduces to the circuit-construction and possible-world result.
Why not just score keys with coverage, discriminability, or κ? These scalars cannot express which source a link depends on. The file already reports that coverage and discriminability selected candidates scoring 0.34 F-measure where a better candidate reached 0.95 (A Study of the Discovery and Redundancy of Link Keys). Several Link Keys are Better than One notes that κ degrades when dataset sizes diverge. We include κ selection as a baseline anyway, in case its weaknesses on clean data do not carry over to noisy data.
Why not just sample possible worlds and re-mine the lattice in each? Mining is already expensive: Linkex took 6 minutes 50 seconds on 12.3M descriptions in one deterministic run (Linkex), and ProvSQL found knowledge compilation outperformed naive sampling (ProvSQL). For In-keys, our monotonicity result makes per-world re-mining unnecessary. Sampling over the fixed circuit remains a legitimate fallback when compilation blows up, and we report where that happens.
Why not just use a noisy-OR over keys? It is cheap and may be enough when the selected keys use disjoint properties. That case is our ablation. We expect it to fail precisely when keys share property pairs, and we measure the gap as a function of that overlap.
Proposed Experiments
We use the benchmarks the link-key papers already use: OAEI 2010 Person1, Person2 and Restaurants; the nine DB-Yago tasks; and the BnF/ABES Libraries task for scale. None of these carry native value-level uncertainty. We therefore inject it under a controlled model and say so explicitly. Each triple is kept, perturbed, or dropped with a probability drawn per property. That probability is exposed to the methods as the token's probability, as an extractor confidence would be. The decisive condition corrupts a minority of properties heavily and leaves the rest clean.
Metrics are F-measure, precision, and recall against reference links; Brier score and calibration of link probabilities, where our method and the two-stage baseline compete and crisp methods abstain; and circuit size, compile time and total time against the Linkex timings (155 candidates in 2 minutes 10 seconds on Sample 1, 186 in 6 minutes 50 seconds on Sample 2). ProvSQL reports provenance overhead of "a small constant factor" on relational workloads. We will check whether that holds for link-key circuits, where token sharing across keys may make compiled forms much larger.
We run four decisive checks. The first verifies on small instances that probabilities from the compiled circuit match exhaustive possible-world enumeration of re-mined lattices exactly. The second is the uneven-corruption comparison against the two-stage pipeline, described above, which tests the core selection claim. The third plots our gain over the noisy-OR ablation against property-pair overlap among selected keys, which tests the correlation claim. The fourth checks at zero injected noise that we recover the crisp baselines' F-measures, which confirms the machinery costs nothing in accuracy when there is nothing to model. We would abandon the selection claim if the second check showed no gain at any noise level, and narrow the work to exact link scoring.
References
- Several Link Keys are Better than One, or Extracting Disjunctions of Link Key Candidates
- Linkex: A Tool for Link Key Discovery Based on Pattern Structures
- ProvSQL: Provenance and Probability Management in PostgreSQL
- Database Theory in Action: Making Provenance and Probabilistic Database Theory Work in Practice (Invited Talk)
- Revisiting Semiring Provenance for Datalog
- Link key candidate extraction with relational concept analysis
- Representation, Provenance, and Explanations in Database Theory and Logic (Dagstuhl Seminar 24032)
- A Study of the Discovery and Redundancy of Link Keys Between Two RDF Datasets Based on Partition Pattern Structures
- Discovering a Representative Set of Link Keys in RDF Datasets