When a question spans several organizations' private knowledge graphs, a federated query engine has to decide which organizations to contact and whether the links between their vocabularies can be trusted. Today both decisions are made on syntax: contact whichever client owns a relation name, and trust whatever entity alignment was learned. Both fail once vocabularies diverge. The same relation can live in three clients under three names, and an alignment can be wrong without contradicting any axiom. This note proposes measuring, per query, how the evidence each client contributes splits into three kinds. It can be redundant (several clients could supply it alone), unique (only one client has it), or synergistic (it only emerges when clients are combined, as in a multi-hop join across an alignment). That measurement would drive both routing and misalignment detection.
The obstacle is cost. Partial information decomposition (PID), the formal tool for that split, has a number of components that grows with the Dedekind numbers: 166 for four sources, 7,581 for five, and over 7.8 million for six. The Dedekind numbers count monotone Boolean functions. A federated conjunctive or disjunctive query is itself a monotone Boolean function over which clients' facts are needed. The idea is therefore to let the logical shape of the query tell us which few components can be nonzero, compute only those, and treat any information left over as a measurable signal that the federation is not behaving as its alignments claim.
Core Claim
The redundancy lattice is the ordered set of PID components. Bits and pieces formalizes it as antichains of source sets ordered by logical implication, which is exactly why its size follows the Dedekind sequence. We supply the missing step for the federated case.
For a query $q$ evaluated over $n$ clients, let $\varphi_q$ be the monotone formula whose satisfying sets are the client subsets that jointly hold a complete proof of an answer, given the current cross-client alignments. Let $\mathcal{A}_q$ be the set of lattice nodes built from $\varphi_q$'s minimal satisfying sets and their combinations. Its size grows with the number of such minimal sets, typically a handful, rather than with the Dedekind number of $n$.
We claim three things:
- Under correct alignment, nearly all information that the clients' answer scores $X_1,\dots,X_n$ carry about answer membership $Y$ lies on $\mathcal{A}_q$.
- Restricting the decomposition to $\mathcal{A}_q$ makes per-query decomposition cheap enough to drive routing over 5 to 10 clients.
- The information that falls outside $\mathcal{A}_q$ detects silent misalignments that logic-based repair cannot see.
The off-structure information is measured by a residual:
$$L_q = I(X_1,\dots,X_n;Y) - \sum_{\alpha \in \mathcal{A}_q} \Pi(\alpha),$$
Here $I$ is the total mutual information between client scores and the answer, estimated directly. $\Pi(\alpha)$ is the PID component at node $\alpha$, obtained by inverting redundancy values computed only at nodes in $\mathcal{A}_q$, under the assumption that components off $\mathcal{A}_q$ vanish. $L_q$ is the information that assumption fails to account for. It is the honesty check on the whole approach: if $L_q$ is large on correctly aligned federations, the claim is false.
Research Program
The query engine. The substrate is FedNGDB. Learning Federated Neural Graph Databases answers multi-hop, intersection and union queries across clients. It splits queries into atomic sub-queries, aligns shared entities with learned mapping matrices, and adds Laplacian noise for local differential privacy. Its decomposition is purely structural and assumes the mapping matrices are correct. We reuse its architecture and add three things.
The decomposition step. The first addition is a compiler from the query graph plus the current alignment to $\varphi_q$ and $\mathcal{A}_q$. The second is a restricted PID estimator on that node set. Each client's sub-query answer score is a source, and the target is answer membership on validation queries.
The redundancy measure follows the shared-exclusion view in Bits and pieces and its k-nearest-neighbor continuous variant by Ehrlich. We evaluate it pointwise in the style of LSMI. Efficient Quantification of Multimodal Interaction at Sample Level splits pointwise mutual information into positive and negative parts and cut runtime from 13 hours to 11 minutes on UCF-101, but only for two sources. Our extension to $n$ sources works because $\mathcal{A}_q$, not the full lattice, sets the cost.
Two uses of the output. The decomposition then drives two decisions:
- Routing under a budget. Drop a client if its unique and synergistic components on $\mathcal{A}_q$ are negligible. Among mutually redundant clients, keep one. Each skipped client saves bandwidth and privacy budget.
- Alignment diagnosis. Flag a mapping when the residual $L_q$ rises sharply on queries routed through it, or when synergy that $\varphi_q$ predicts should appear across it collapses.
The privacy constraint. Client scores are perturbed with Laplacian noise, and Gaussian PID shows that plug-in information estimates are badly biased at small or noisy samples. We therefore report every estimate at FedNGDB's noise levels and fit a simple noise-aware bias correction. This is a constraint on the method, not its contribution.
Positioning against related work. Other uses of decomposition motivate but do not supply this design. Emergent Coordination in Multi-Agent Language Models applies PID to agents with a shared action space on a toy guessing task, with no schemas and no scalability concern. The coarse metrics in Characterising directed and undirected metrics of high-order interdependence and the score-based estimator S$\Omega$I avoid the lattice, but they report only a net balance in which redundancy and synergy can cancel. That is precisely the failure that matters when two duplicated clients and one join coexist in the same query.
Baselines
Contact all clients. The naive reference is FedNGDB contacting every client for every query with its original structural decomposition. It gives the accuracy ceiling at maximal communication and privacy cost. No reported result found on Lacuna for FedNGDB's complex-query accuracy on FB15k-237, FB15k, or NELL995, so we rerun it ourselves on identical partitions and noise settings.
Syntactic routing. The strongest existing routing method is the same engine with FedNGDB-style decomposition, sending each atomic sub-query to the client that owns the relation name. Under heterogeneity we resolve names via the learned alignment. This is the actual competitor: it costs nothing to compute and is what a practitioner would deploy. Beating it means matching contact-all accuracy within one Hits@3 point while contacting fewer clients, on partitions where relations are duplicated under different names.
Label-driven routing. Two cheap data-driven routers get the same validation queries, the same estimator backbone and the same tuning budget as our method. Leave-one-client-out drops a client if removing it costs no validation accuracy. Greedy pairwise mutual information adds clients in order of marginal information.
Misalignment detection. The competitors are confidence thresholding on mapping scores and the logic-based repair of Improving Automatically Created Mappings Using Logical Reasoning. That method removed only incorrect rules on OntoFarm and found 50% to 85% of bridge rules redundant, but it reacts only to unsatisfiability. We implement the repair side using the BERTMap repair module (KRR-Oxford/BERTMap). For context, BERTMap reports F1 gains over AML of 1.4% and over LogMap of 4.2% on FMA-SNOMED.
Ablations. The key ablation keeps everything fixed but replaces $\mathcal{A}_q$ with a random node set of the same size. If routing and detection survive this swap, the query structure is doing no work. A second ablation replaces the restricted decomposition with O-information gating, to test whether net measures suffice. For three clients we also compute the full 18-component lattice as a gold reference, which lets us check $L_q$ against the true off-structure mass.
Why not just…?
Why not just do leave-one-client-out ablation? It sums each client's unique and synergistic contribution, which is close to what routing needs. It is therefore a real threat on partitions without duplication. It breaks under redundancy, though. When two clients hold the same relation under different names, removing either one costs nothing, so the router drops both and the answer disappears. Our partitions include exactly this case. If leave-one-out matches us on those partitions at equal validation cost, the decomposition adds nothing to routing, and we will report that.
Why not just use pairwise mutual information or O-information? Pairwise measures cannot see synergy, which is the defining property of cross-client joins: neither client's score alone predicts a chained answer. O-information sees synergy only as a net balance, and Characterising directed and undirected metrics of high-order interdependence shows it cannot tell zero interaction from redundancy and synergy cancelling. The O-information ablation tests this directly on mixed queries that combine duplicated clients with a cross-client hop.
Why not just rely on logical repair to catch bad alignments? Repair catches only mappings that make some class unsatisfiable, a limitation the repair paper's own setting implies. A type-consistent swap, such as aligning two different cities, violates nothing. We inject both kinds of corruption and report detection AUROC separately for errors that repair catches and errors it cannot. Our method needs to win only on the second group. Using it alongside repair is the intended deployment.
Why not just centralize and run one aligner and reasoner? Privacy rules and scale motivate federation in the first place, per Learning Federated Neural Graph Databases and Scalability Study of Peer-to-Peer Consequence Finding. We still run a centralized model as an oracle upper bound, not as a deployable competitor.
Proposed Experiments
Data and partitions. We use FB15k-237 with the clustered (C3, C5, C10) and random (R3, R5, R10) partitions from FedLU, plus FB15k and NELL995 over 3, 5 and 10 clients as in FedNGDB. Query types are the standard path, intersection, union and mixed forms. FedLU's reported 57.53% Hits@10 for TransE on C3 is a link-prediction number. It serves only to sanity-check our embeddings, not as a query-answering target.
Injected heterogeneity. We introduce three kinds of heterogeneity under controlled rates:
- relation renaming per client;
- duplication of relations across clients under different names;
- corruption of entity alignments, split into swaps that logical repair would catch and type-consistent swaps it would not.
Metrics. We measure query accuracy (MRR and Hits@3 per query type), clients contacted per query, bytes sent, and privacy budget spent. For diagnosis we measure detection AUROC on corrupted mappings. For cost we measure estimator wall-clock time against the number of clients.
Decisive checks. The project stands or falls on four checks.
- On correctly aligned federations at 3 clients, $L_q$ must be small relative to total information, and the restricted components must match the full-lattice gold values. If not, the query-structure assumption is wrong.
- The random-node-set ablation must degrade both routing and detection.
- On the duplicated-relation partitions, routing must beat leave-one-client-out and syntactic routing in the accuracy-versus-clients-contacted tradeoff at matched validation cost.
- Detection AUROC on type-consistent swaps must clearly exceed confidence thresholding while repair scores at chance on that group.
Estimator time should grow with the number of minimal satisfying sets rather than with the number of clients. We will plot it from 3 to 10 clients against full-lattice computation wherever the full lattice remains feasible.
References
- Bits and Pieces: Understanding Information Decomposition from Part-whole Relationships and Formal Logic
- Learning Federated Neural Graph Databases for Answering Complex Queries from Distributed Knowledge Graphs
- Partial information decomposition for continuous variables based on shared exclusions: Analytical formulation and estimation
- Efficient Quantification of Multimodal Interaction at Sample Level
- Gaussian Partial Information Decomposition: Bias Correction and Application to High-dimensional Data
- Emergent Coordination in Multi-Agent Language Models
- Characterising Directed and Undirected Metrics of High-Order Interdependence
- S$\Omega$I: Score-based O-INFORMATION Estimation
- Improving Automatically Created Mappings Using Logical Reasoning
- BERTMap: A BERT-Based Ontology Alignment System
- Scalability Study of Peer-to-Peer Consequence Finding
- Heterogeneous Federated Knowledge Graph Embedding Learning and Unlearning