Cost Characterization of Vertically Partitioned Federated Knowledge Graphs

1. Introduction

• Vertical partitioning splits relation subsets across organizations sharing an entity space, so a multi-hop answer may require facts from multiple silos.This differs from horizontal federation, where parties hold the same relations over different entities.Source: §1 · p. 1
• Placing frequently chained relations together shortens cross-silo paths but can unbalance silos, while even spreading relations balances load but lengthens paths.The resulting trade-off matters most where each silo can hold several relations.Source: §1 · p. 2
• The paper formalizes relation-to-silo assignment through four strategies and five cost metrics, finding that only locality and balance vary with the partition.The strategies are semantic domain grouping, frequency balancing, co-occurrence graph cuts, and random assignment; the fixed model isolates partition effects.Source: §1 · p. 2

2.1. Partitioning and Physical Design for Graph Data

• Graph partitioning work repeatedly finds a tension between balancing storage and preserving query paths, while this paper studies that tension in a learned retrieval pipeline under ownership and privacy boundaries.Here, local embeddings, server-side fusion, and candidate ranking mediate partition cost; raw triples cannot cross silos.Source: §2.1 · p. 3

2.2. Federated Knowledge Graphs and Question Answering

• Figure 2 illustrates four strategies across nine relations and three silos: topic grouping, triple-count equalization, keeping chained relations together, and random assignment.The figure presents the partitioning alternatives that motivate the paper's cost comparison.Source: Figure 2 · p. 4
• Federated embedding work generally assumes a fixed partition, while prior vertical-federated question answering establishes feasibility but focuses on answer quality rather than partition costs.The related work contrasts feature partitioning with relation partitioning, where reasoning paths can cross silo boundaries.Source: §2.2 · pp. 3–4

3.1. Problem Setup and Notation

• The design problem is an assignment of relations to silos; partitions of the same graph and silo count can differ in silo sizes and cross-silo reasoning paths.The relation subsets are disjoint and cover the relation vocabulary, while the entity space is shared and triples remain distributed.Source: §3.1 · p. 4

3.2. Semantic Domain Partitioning (Πdom)

• Semantic domain partitioning keeps each domain indivisible, modeling inherited organizational ownership, but can leave silos unbalanced or separate frequently chained relations.When silos outnumber domains, surplus silos remain empty; when chained relations belong to different domains, queries cross silo boundaries.Source: §3.2 · pp. 4–5

3.3. Frequency-Balanced Partitioning (Πfreq)

• Frequency-balanced partitioning greedily assigns the largest relation sets to the lightest silo, targeting equal triple counts but ignoring query locality.It can separate relations chained by queries, lengthening cross-silo paths.Source: §3.3 · p. 5

3.4. Co-occurrence Graph-Cut Partitioning (Πcut)

• Co-occurrence graph-cut partitioning minimizes the weight of cross-silo edges while constraining silo sizes, using training-path relation co-occurrences to target locality.Its greedy weighted-clustering heuristic uses a 25% slack cap and may accept more imbalance than frequency balancing.Source: §3.4 · p. 5

3.5. Random Partitioning (Πrand)

• Random partitioning assigns relations uniformly at random and serves as a reference that optimizes neither balance nor locality.The authors average twenty seeds for structural metrics and three for metrics requiring training.Source: §3.5 · p. 5

3.6. Computing the Partitions

• The five-metric comparison identifies cross-silo path length and load balance as the partition-dependent axes; the other three are fixed by the graph and silo count.Figure 3 compares layouts for K∈{3, 5, 7}, with within-K differences reflecting the partition.Source: Table 1 · p. 6, Figure 3 · p. 6

• Every strategy uses the same pipeline: silos train local TransE models and upload entity embeddings, while a frozen BERT encoder feeds question representations into server-side candidate scoring.Raw triples and relation embeddings stay within silos; the server fuses entity embeddings and scores candidates in the joint space.Source: §4 · p. 6, Figure 4 · p. 7
• Per-round communication is fixed at a given silo count because each silo uploads its entity embeddings and receives a gradient slice.Total communication also depends on the training-round count.Source: §4 · p. 6
• Candidate index size is the mean size of each topic entity’s pooled two-hop candidate set, which depends on the graph rather than the partition.Pooling across silos preserves chains whose two hops lie in different silos.Source: §4 · p. 7
• Cross-silo path length counts relation transitions assigned to different silos; on two-hop workloads, it equals the fraction of queries that cross a boundary.Enrichment-derived single-relation paths contribute no transition.Source: §4 · p. 7
• Load imbalance is the coefficient of variation of per-silo triple counts, while query latency measures end-to-end answering time and should not vary by partition beyond measurement noise.Synchronized rounds are bounded by the heaviest silo; latency includes candidate lookup, question encoding, topic anchoring, and scoring.Source: §4 · pp. 7–8
• Only cross-silo path length and load balance vary with the partition; communication, candidate index size, and query latency are determined by the graph, substrate, and silo count.Pooled candidate construction makes the scored set independent of the partition, and latency is downstream of that set.Source: §4 · pp. 6, 8

5. Experimental Setup

• MetaQA and PathQuestion use their two-hop splits; offline enrichment grows MetaQA from nine to fifteen relations, while PathQuestion remains at thirteen.PathQuestion has a larger entity space but fewer triples, whereas MetaQA is denser over fewer entities.Source: §5 · p. 8
• TransE embeddings and a frozen BERT question encoder with a trainable projection head are held constant to isolate partition effects.The study does not sweep alternative embeddings or encoders.Source: §5 · p. 8
• All cells share the training configuration, including 256-dimensional local embeddings, while partition and silo count are the only changing quantities.Candidate construction expands two hops with first- and second-hop neighbor caps of 50 and 20, respectively, retaining at most 100 neighbors per entity.Source: §5 · p. 8
• Each dataset uses four partitioning strategies at 3, 5, and 7 silos, with each relation assigned to one silo and the entity space shared.Random partitioning is averaged over twenty seeds for structural metrics and three seeds for quality control and total communication to target.Source: §5 · p. 9
• Breadth-first search recovers shortest topic-to-answer paths; the cut strategy uses training-path co-occurrences, while cross-silo path length is measured on held-out test paths.When multiple paths exist, the shortest is only a proxy for the intended reasoning chain.Source: §5 · p. 9
• The protocol targets validation Hits@3 of 0.70 on MetaQA and 0.55 on PathQuestion, treating quality as a control rather than a claimed result.Most cells clear the target early, so differences in rounds to target are small and may reflect run-to-run variation.Source: §5 · p. 9

6. Results

• Hits@3 is matched on MetaQA but only loosely matched on PathQuestion, whose 1,524-question training set accompanies a wider 0.661-to-0.831 range.The authors treat quality as a control rather than a claimed result, so PathQuestion cost comparisons are approximate.Source: §6 · p. 9
• 0.000 crossing rate for Πcut at K=3 and K=5 on MetaQA, versus 0.019 for Πdom and 0.048 and 0.053 for Πrand, respectively; all strategies stay at or below 0.06.Πcut ties for best at K=7, and partitioning has limited practical effect on MetaQA locality.Source: §6 · p. 9
• 47% lower crossing rate for Πcut than the inherited partition on PathQuestion at K=3; on transition-capable queries, crossings fall from 82% to 44%.At K=5 and K=7, Πcut no longer leads; the balance cap leaves room for only two relations per silo at K=7, too little freedom to co-locate a chain.Source: §6 · pp. 9–10
• Πfreq achieves the lowest imbalance in all six dataset-and-silo-count combinations; at K=3 its imbalance is 0.018 on MetaQA and 0.012 on PathQuestion.Πdom becomes worst-balanced at K≥5, with imbalance rising from 0.371 to 1.286 on MetaQA and from 0.609 to 1.483 on PathQuestion as surplus empty silos inflate the coefficient of variation.Source: §6 · p. 10, Figure 5 · p. 11
• At K=3, Πcut leads on locality while Πfreq leads on balance; the conflict weakens as K grows, and no strategy is best on both axes.At K≥5, Πfreq is at least as good as Πcut on both axes for PathQuestion at K=5; at K=7 it gives up 0.018 on crossing rate while holding roughly half the imbalance.Source: §6 · p. 10, Figure 6 · p. 11, Figure 5 · p. 11
• 144.3 entries per topic entity on MetaQA and 103.6 on PathQuestion remain constant across strategies; query latency averages 10.5 ms and 10.0 ms, respectively.Candidate construction pools candidates independently of partition, while per-round communication is fixed by silo count.Source: §6 · p. 10
• Across three Πrand training seeds at K=5, bytes to target vary twofold, as widely as between strategies; convergence differences fall within training variance.The authors recommend choosing partitions for locality or balance, not to reduce training bandwidth or query time.Source: §6 · p. 11
• The authors expect guidance to transfer by relations per silo, |R|/K, but have not verified it on a large vocabulary.Their benchmarks reach the thin-relation regime at K=7 only because |R| is small; a 200-relation federation would reach it near K=100.Source: §6 · p. 11

7. Conclusion

• At K=3 on PathQuestion, Πcut cuts the crossing rate from 0.517 to 0.276, while Πfreq has the lowest imbalance in every cell.The locality advantage is strongest when each silo can hold several relations; it weakens as K grows.Source: §7 · p. 12
• Three of the five cost metrics are graph-and-silo-count invariants, leaving cross-silo path length and load balance as the partition-dependent trade-off.The study formalizes relation-to-silo assignment as a design space and defines five cost metrics.Source: §7 · p. 12
• Federations with room to co-locate reasoning paths should favor Πcut; deployments constrained by their slowest silo or spread across many silos should favor Πfreq.At higher K, Πfreq becomes competitive on locality while retaining its balance advantage.Source: §7 · p. 12
• The benchmarks have fewer than twenty relation types, so the thin regime arrives at K=7; extending the regime pattern to larger vocabularies remains a conjecture.Πcut uses a greedy heuristic over recovered rather than annotated paths, which biases M3 and the method it evaluates in the same direction.Source: §7 · p. 12
• The four heuristics do not directly optimize the trade-off; a partitioner minimizing weighted cut and imbalance could trace the frontier between the two axes.Larger vocabularies, drifting workloads, and partial entity alignment are also identified as next steps.Source: §7 · p. 12

Declaration on Generative AI

• Claude was used for language editing and structural refinement; authors reviewed the content and state that it produced no research findings, results, or citations.The authors take responsibility for the submission and state that this use complies with CEUR’s Policy on AI-Assisting Tools.Source: Declaration on Generative AI · p. 12