Analysis reveals trade-offs in cutting knowledge graph data across silos
Cost Characterization of Vertically Partitioned Federated Knowledge Graphs
Artificial IntelligenceDatabasesInformation Retrieval
Summary
Knowledge graphs store facts across different organizations, each holding different parts. Figuring out how to split these parts affects the speed and cost of answering questions that need data from multiple places. The authors compare four ways to split the data and measure their impact on communication, workload balance, and query speed. They find that only some costs depend on the splitting method while others depend on the graph size and number of silos. This helps choose the best splitting method depending on whether you want faster answers or balanced workloads.
What this means in practice
- •For data engineers: Optimize data partitioning strategies in distributed knowledge graph systems to balance query speed and server load.
- •For cloud service operators: Configure federated query systems to reduce cross-organization communication costs while maintaining balanced workloads across servers.
Authors
Md Saikat Islam Khan Bappy, Oshani Seneviratne
Abstract
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.