# Cost Characterization of Vertically Partitioned Federated Knowledge Graphs

arXiv: https://arxiv.org/abs/2609.13664 · HTML: https://mlsanity.com/paper/2609.13664/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 28 references that are in the map.
- First posted on arXiv 12 Sep 2026.

## Builds on (most cited first, 17 of 17)

- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Variational Reasoning for Question Answering with Knowledge Graph](https://mlsanity.com/paper/1709.04071/) (2017)
- [An Interpretable Reasoning Network for Multi-Relation Question Answering](https://mlsanity.com/paper/1801.04726/) (2018)
- [FedE: Embedding Knowledge Graphs in Federated Setting](https://mlsanity.com/paper/2010.12882/) (2020)
- [Heterogeneous Federated Knowledge Graph Embedding Learning and Unlearning](https://mlsanity.com/paper/2302.02069/) (2023)
- [Large Language Models Meet Knowledge Graphs for Question Answering: Synthesis and Opportunities](https://mlsanity.com/paper/2505.20099/) (2025)
- [LLM-Based Multi-Hop Question Answering with Knowledge Graph Integration in Evolving Environments](https://mlsanity.com/paper/2408.15903/) (2024)
- [OpenFGL: A Comprehensive Benchmark for Federated Graph Learning](https://mlsanity.com/paper/2408.16288/) (2024)
- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [A Survey of RDF Stores & SPARQL Engines for Querying Knowledge Graphs](https://mlsanity.com/paper/2102.13027/) (2021)
- [Quantifying and Defending against Privacy Threats on Federated Knowledge Graph Embedding](https://mlsanity.com/paper/2304.02932/) (2023)
- [Learning Federated Neural Graph Databases for Answering Complex Queries from Distributed Knowledge Graphs](https://mlsanity.com/paper/2402.14609/) (2024)
- [Fed-RD: Privacy-Preserving Federated Learning for Financial Crime Detection](https://mlsanity.com/paper/2408.01609/) (2024)
- [Personalized Federated Knowledge Graph Embedding with Client-Wise Relation Graph](https://mlsanity.com/paper/2406.11943/) (2024)
- [A Differentially Private Blockchain-Based Approach for Vertical Federated Learning](https://mlsanity.com/paper/2407.07054/) (2024)
- [FedV-KGQA: Multi-Hop Question Answering over Vertically Partitioned Knowledge Graphs](https://mlsanity.com/paper/2608.24846/) (2026)
- [Low-Dimensional Federated Knowledge Graph Embedding via Knowledge Distillation](https://mlsanity.com/paper/2408.05748/) (2024)

## Abstract (arXiv)

Knowledge graphs are increasingly distributed across autonomous organizations that share an entity space but own disjoint subsets of relations, forming a vertical partition. Answering a multi-hop query may require combining facts from several silos, making the partitioning strategy a key data management decision that affects communication, indexing, load balance, and query latency. However, the costs associated with different partitioning strategies remain insufficiently studied. We formalize vertical partitioning as a design space and compare four strategies: semantic domain grouping, frequency-balanced partitioning, co-occurrence graph-cut partitioning, and random partitioning. We evaluate them using five metrics: communication cost, candidate index size, cross-silo path length, load balance, and end-to-end query latency. Three of the five prove to be determined by the graph and the silo count rather than by the partition, which reduces the design problem to two conflicting axes, cross-silo path length and load balance. Experiments on MetaQA and PathQuestion use a fixed federated knowledge graph question-answering architecture based on TransE embeddings and a frozen BERT encoder across three silo configurations. By keeping the learning model unchanged, we isolate the effect of partitioning and show that the trade-off between locality and balance holds only where each silo can hold several relations, weakening as the number of silos increases. The study provides practical guidance for deployments constrained by cross-silo reasoning or by silo load.