Cost Characterization of Vertically Partitioned Federated Knowledge Graphs

# Cost Characterization of Vertically Partitioned Federated Knowledge Graphs
Source: [https://arxiv.org/html/2609.13664](https://arxiv.org/html/2609.13664)
###### 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\.

###### keywords

Federated Knowledge Graphs ,Vertical Partitioning ,Federated Question Answering ,Data Management Cost Analysis ,Graph Partitioning

††copyrightyear:2026††copyright:Copyright for this paper by its authors\. Use permitted under Creative Commons License Attribution 4\.0 International \(CC BY 4\.0\)\.††venue:DMKG’26: 2nd International Workshop on Data Management for Knowledge Graphs, October 2026, Bari, Italy††email:islamm9@rpi\.edu††email:senevo@rpi\.edu††address:Rensselaer Polytechnic Institute, Troy, NY 12180, USA## 1Introduction

The Web of knowledge graphs is not a single queryable store but an ecosystem of autonomous sources\. In many real deployments, facts about the same entities are distributed across organizations that each hold a different slice of the relation vocabulary: a film studio records who directed a film, a streaming platform who starred in it, a metadata service its genre\. All three describe the same entities, but no party holds the whole graph, and raw data cannot be centralized due to governance, commercial sensitivity, and data sovereignty constraints\. This is a*vertical partition*of a knowledge graph: the entity space is shared, while the relations are split into disjoint, privately held subsets\. It differs fundamentally from the horizontal federation studied by most federated knowledge graph work[Hu et al\. \(2025\)](https://arxiv.org/html/2609.13664#bib.bib25);[Gunti et al\. \(2025\)](https://arxiv.org/html/2609.13664#bib.bib24);[Chen et al\. \(2024a\)](https://arxiv.org/html/2609.13664#bib.bib5), where every party holds the same relations over different entities and can often answer a query within its own shard\.

Under vertical partitioning, that locality is lost\. Answering a multi\-hop query means chaining facts that are split across parties by design: a reasoning path may begin in one silo, pass through a shared entity, and end in another\. The question*“Which actors starred in films directed by Nolan?”*requires the directing relation held by the studio and the acting relation held by the platform, so neither party can answer it alone\. Every hop that crosses a silo boundary plays the same role as a distributed join plays in a relational federation, since it forces evidence held by two owners to be combined \(Figure[1](https://arxiv.org/html/2609.13664#S1.F1)\)\. The ingredients for answering such questions exist separately: embedding\-based methods rank answers to multi\-hop questions over a centralized graph[Saxena et al\. \(2020\)](https://arxiv.org/html/2609.13664#bib.bib9), and federated embedding methods learn representations across parties without sharing raw triples[Chen et al\. \(2021\)](https://arxiv.org/html/2609.13664#bib.bib1)\. Recent work has combined them to show that multi\-hop question answering is achievable over a vertically partitioned graph, by training local embeddings within each silo and fusing them on a server[Bappy and Seneviratne \(2026\)](https://arxiv.org/html/2609.13664#bib.bib26)\. That line of work, however, treats the partition as a fixed input and focuses on answer quality\.

#### A note on what each silo exposes:

The vocabulary of this paper is drawn from data management, and terms such as distributed join and cross\-silo hop describe the shape of the workload rather than the mechanism that serves it\. No silo in our setting exposes a query endpoint, and no silo evaluates a subquery over its own triples\. A silo releases only derived quantities, here, a local entity embedding matrix\. A question is answered by ranking candidate entities in a fused embedding space, not by planning and executing a distributed query\. This constraint is what makes the assignment of relations to silos a physical design decision with real consequences\. There is no runtime optimizer that can reorder, push down, or cache its way around a poor layout, so whatever a partition costs in cross\-silo reasoning it costs on every query\.

A prior and equally practical question has been largely overlooked: given a relation vocabulary and a set of silos,*how should the relations be assigned to silos, and what storage and query costs does each assignment incur?*This is squarely a data management problem\. It concerns partitioning, indexing, federated query processing, and the communication that federation entails, and its answer is not cosmetic\. Placing tightly co\-used relations in the same silo shortens the cross\-silo paths a query must traverse, but it can leave silos badly unbalanced in size, so that one overloaded silo throttles every synchronized round\. Spreading relations evenly balances the load but separates relations that are frequently chained, lengthening cross\-silo paths\. A partition that is good on one axis is often poor on the other, at least where each silo can hold several relations, and the same query workload can be cheap or expensive to serve depending entirely on how the relations were divided\. These are exactly the trade\-offs a practitioner must reason about when deploying a federated knowledge graph, yet there is no systematic account of them: a practitioner today chooses a partition, or inherits one, with no way to know what it costs or how far it sits from the best achievable\.

This paper provides that characterization\. We treat partitioning as the object of study rather than a fixed input, formalize it as an assignment of the relation vocabulary to silos, and define a small space of strategies that span the natural axes of the problem: semantic domain grouping, which reflects the partition an organization typically inherits; frequency\-balanced partitioning, which equalizes the data held by each silo; co\-occurrence graph\-cut partitioning, which keeps frequently chained relations together to preserve locality; and random partitioning, which optimizes nothing and serves as a baseline\. We measure the consequences of each strategy along five data management metrics, namely communication cost, candidate index size, cross\-silo path length, load balance, and end\-to\-end query latency\. Three of these prove to be invariants of the graph and the silo count, leaving locality and balance as the two axes a partition actually trades off\. Crucially, we hold the learning model fixed, evaluating every strategy on the same federated question answering substrate built on TransE[Bordes et al\. \(2013\)](https://arxiv.org/html/2609.13664#bib.bib10)and a frozen BERT encoder[Devlin et al\. \(2019\)](https://arxiv.org/html/2609.13664#bib.bib11), so that at each silo count every difference in cost is attributable to the partition\. Our contributions are as follows\.

- •Vertical partitioning as a design space\.We formalize the relation\-to\-silo assignment problem for vertically partitioned knowledge graphs and define four concrete strategies spanning the natural axes of the space\.
- •A data management cost model\.We define five measurable cost metrics, namely per\-round communication, candidate set and index size, cross\-silo path length, load balance, and query latency\. Together they capture what a partition costs to store and query\. We further show that three of the five are invariants of the graph and the silo count rather than consequences of the partition, so the partitioning decision reduces to a two\-dimensional trade\-off\.
- •An empirical characterization\.Across two benchmarks and three silo counts, holding the learning model fixed, we quantify the trade\-offs each strategy makes and distill practical guidance on which strategy suits which deployment objective\.

![Refer to caption](https://arxiv.org/html/2609.13664v1/Figure1.png)Figure 1:Multi\-hop question answering in the vertical federated setting\. Silos own disjoint relation subsets over a shared entity spaceEE, so a 2\-hop question may chain facts across a silo boundary\.

## 2Related Work

### 2\.1Partitioning and Physical Design for Graph Data

How a graph dataset is laid out determines how expensive it is to query, and choosing that layout has long been recognized as a core data management decision\. In RDF data management, SW\-Store[Abadi et al\. \(2009\)](https://arxiv.org/html/2609.13664#bib.bib6)introduced vertically partitioned storage, grouping triples by predicate so that a query touching only a few predicates scans little data\. Balanced graph partitioning remains an active area, and recent surveys catalogue the maturity of the underlying machinery[Çatalyürek et al\. \(2023\)](https://arxiv.org/html/2609.13664#bib.bib15);[Ali et al\. \(2022\)](https://arxiv.org/html/2609.13664#bib.bib7), while systems work continues to improve partition quality at scale, as in streaming partitioners that reduce both edge cuts and worker imbalance\. Most similar to our locality\-oriented strategy is application\-driven partitioning[Fan et al\. \(2023\)](https://arxiv.org/html/2609.13664#bib.bib14), which selects a layout from the workload that will run over it rather than from graph topology alone\. Empirical comparisons of RDF partitioning strategies[Akhter et al\. \(2018\)](https://arxiv.org/html/2609.13664#bib.bib8)confirm the recurring tension we also study: partitioning to balance storage tends to sever the join paths that queries traverse, so the layout minimizing imbalance is rarely the layout minimizing cross\-partition traffic, and no single scheme is uniformly best\.

Our work adopts this physical design perspective but differs on two axes that prior partitioning work does not combine\. First, the query is a*natural language multi\-hop question*answered by embedding\-based ranking, not a structured query with an explicit plan\. The cost of a partition is therefore mediated by a learned retrieval pipeline, namely local embedding, server\-side fusion, and candidate ranking, rather than by a relational operator tree, and it is realized through structures such as the per\-silo candidate index that this pipeline builds\. Second, the partition boundary coincides with an*ownership and privacy*boundary: relations are held by autonomous organizations, raw triples cannot cross a silo, and a cross\-partition join is a round of federated communication between parties that never expose their data rather than an intra\-cluster shuffle\. Together these change both what a partition costs and which partitions are admissible\. To our knowledge, the cost of alternative relation\-to\-silo assignments has not been characterized under these conditions, which is the gap this paper addresses\.

### 2\.2Federated Knowledge Graphs and Question Answering

Two further lines of work provide the substrate on which we measure these costs, though neither studies the partitioning question itself\. Federated knowledge graph embedding learns representations across parties without sharing raw data, but almost exclusively in the*horizontal*setting, where parties hold the same relations over different entities and a query can often be answered within a single shard\. FedE[Chen et al\. \(2021\)](https://arxiv.org/html/2609.13664#bib.bib1)established the pattern of aggregating entity embeddings through a server, and the line has since developed rapidly, targeting heterogeneity and unlearning[Zhu et al\. \(2023\)](https://arxiv.org/html/2609.13664#bib.bib2);[Zhu et al\. \(2025\)](https://arxiv.org/html/2609.13664#bib.bib16), cheaper embedding exchange[Zhang et al\. \(2024\)](https://arxiv.org/html/2609.13664#bib.bib4), personalization[Zhang et al\. \(2025\)](https://arxiv.org/html/2609.13664#bib.bib19), and the privacy and robustness risks of repeated exchange[Hu et al\. \(2023\)](https://arxiv.org/html/2609.13664#bib.bib3);[Jiang et al\. \(2026\)](https://arxiv.org/html/2609.13664#bib.bib18); benchmarks have also matured[Li et al\. \(2025\)](https://arxiv.org/html/2609.13664#bib.bib17)\. This body of work shares our federated framing but assumes the partition is given and targets model quality or privacy, not the cost of the partition itself\. The vertical case, in which a single reasoning path is split across owners by construction, remains comparatively unexplored\. Vertical federation has been studied outside knowledge graphs, where parties hold disjoint feature sets over shared samples[Tran et al\. \(2024\)](https://arxiv.org/html/2609.13664#bib.bib28), and federated learning is used more broadly where data cannot be centralized for regulatory reasons[Khan et al\. \(2024\)](https://arxiv.org/html/2609.13664#bib.bib27)\. In both, the partitioned objects are features rather than relations, so no reasoning path crosses a boundary\.

Question answering over knowledge graphs has likewise advanced\. Embedding\-based methods score candidate answers in a learned space, as in EmbedKGQA[Saxena et al\. \(2020\)](https://arxiv.org/html/2609.13664#bib.bib9), while recent work couples large language models with graph traversal through agentic exploration, retrieved relation paths, or multi\-hop reasoning over evolving graphs[Sun et al\. \(2024\)](https://arxiv.org/html/2609.13664#bib.bib20);[Luo et al\. \(2024\)](https://arxiv.org/html/2609.13664#bib.bib21);[Chen et al\. \(2024b\)](https://arxiv.org/html/2609.13664#bib.bib22);[Ma et al\. \(2025\)](https://arxiv.org/html/2609.13664#bib.bib23)\. These methods assume centralized graph access or centrally available retrieved evidence\. A smaller line extends question answering to vertically partitioned federated graphs, establishing that multi\-hop answers can be recovered without centralizing the graph[Bappy and Seneviratne \(2026\)](https://arxiv.org/html/2609.13664#bib.bib26)\. That work establishes feasibility and optimizes answer quality; it does not ask how the underlying partition should be chosen or what different partitions cost to store and query\. We take such a pipeline as a*fixed*substrate and hold it constant, so that the differences we report are attributable to the partition alone\. Our focus is thus orthogonal and complementary: prior work asks whether questions can be answered over a given partition, whereas we ask how the partition should be chosen and what it costs\.

## 3The Vertical Partitioning Design Space

### 3\.1Problem Setup and Notation

LetG=\(E,R,T\)G=\(E,R,T\)be a knowledge graph with entity setEE, relation setRR, and triple setT⊆E×R×ET\\subseteq E\\times R\\times E\. A*vertical partition*intoKKsilos is an assignmentΠ:R→\{1,…,K\}\\Pi:R\\rightarrow\\\{1,\\dots,K\\\}that gives each siloSkS\_\{k\}a private relation subsetRk=Π−1​\(k\)R\_\{k\}=\\Pi^\{\-1\}\(k\)\. The relation subsets are pairwise disjoint and jointly coverRR, so thatR=⋃k=1KRkR=\\bigcup\_\{k=1\}^\{K\}R\_\{k\}andRi∩Rj=∅R\_\{i\}\\cap R\_\{j\}=\\emptysetfori≠ji\\neq j\. SiloSkS\_\{k\}holds only its local triplesTk=\{\(h,r,t\)∈T:r∈Rk\}T\_\{k\}=\\\{\(h,r,t\)\\in T:r\\in R\_\{k\}\\\}\. The entity spaceEEis shared across all silos, while the full triple setT=⋃kTkT=\\bigcup\_\{k\}T\_\{k\}is never centralized\. Raw triples cannot cross a silo boundary\. As stated in Section[1](https://arxiv.org/html/2609.13664#S1), a silo exposes only derived quantities, and in our substrate that means a local entity embedding matrix\.

The object of study is the assignmentΠ\\Piitself\. Two partitions of the same graph into the same number of silos can differ substantially in silo sizes, in the number of reasoning paths that cross a silo boundary, and in the communication a federated query pipeline must perform, all before any learning takes place\. We consider four strategies that span the natural axes of this space, illustrated in Figure[2](https://arxiv.org/html/2609.13664#S3.F2)for nine relations across three silos\.

![Refer to caption](https://arxiv.org/html/2609.13664v1/Figure4.png)Figure 2:The four partitioning strategies, shown for nine relations across three silos: grouping by topic, equalizing triple counts, keeping chained relations together, and random assignment\.
### 3\.2Semantic Domain Partitioning \(Πdom\\Pi\_\{\\mathrm\{dom\}\}\)

Relations are grouped by their semantic domain, mirroring how an organization naturally owns a coherent slice of the graph, such as all production relations in one silo and all cast relations in another\. Each relationrrcarries a domain labeldom⁡\(r\)\\mathrm\{dom\}\(r\), andΠdom\\Pi\_\{\\mathrm\{dom\}\}treats each semantic domain as an indivisible group\. When domains outnumber silos they share silos; when silos outnumber domains, the surplus silos remain empty\. This models an inherited partition whose ownership boundaries cannot be subdivided merely to occupy additional nodes\. This is the assignment a real federation typically inherits, because each participating organization already owns a semantically coherent set of relations\. It is intuitive and deployment\-realistic, but it optimizes neither balance nor locality\. Balance suffers whenever domains differ in size, and severely so when silos outnumber domains, because the surplus silos receives no relations\. Locality suffers when two domains are frequently chained in queries, such as directing followed by acting, because placing them in different silos forces every such query to cross a boundary\.

### 3\.3Frequency\-Balanced Partitioning \(Πfreq\\Pi\_\{\\mathrm\{freq\}\}\)

Relations are assigned so as to equalize the total triple count per silo\. We use a greedy longest\-processing\-time heuristic\. Relations are sorted by their triple count\|Tr\|\|T\_\{r\}\|in descending order, and each is assigned in turn to whichever silo is currently lightest\. This drives the per\-silo load toward the ideal\|T\|/K\|T\|/K, which directly optimizes load balance and storage uniformity\. What the heuristic does not consider is locality\. Because it weighs only size and never which relations are used together, it routinely separates relations that queries chain, lengthening cross\-silo reasoning paths\.

### 3\.4Co\-occurrence Graph\-Cut Partitioning \(Πcut\\Pi\_\{\\mathrm\{cut\}\}\)

This strategy explicitly targets locality\. We build a weighted relation co\-occurrence graphGR=\(R,W\)G\_\{R\}=\(R,W\)whose nodes are the relations\. Its edge weightw⁡\(ri,rj\)w\(r\_\{i\},r\_\{j\}\)counts how oftenrir\_\{i\}andrjr\_\{j\}appear, in either order, as consecutive hops on a reasoning path in the training query workload:

w⁡\(ri,rj\)=∑q𝟏​\[ri,rj​consecutive on the path of​q\]\.w\(r\_\{i\},r\_\{j\}\)=\\sum\_\{q\}\\mathbf\{1\}\\big\[\\,r\_\{i\},r\_\{j\}\\text\{ consecutive on the path of \}q\\,\\big\]\.\(1\)The objective is to minimize the total weight of edges whose endpoints fall in different silos,

minΠ∑i<jw\(ri,rj\)⋅𝟏\[Π\(ri\)≠Π\(rj\)\],\\min\_\{\\Pi\}\\sum\_\{i<j\}w\(r\_\{i\},r\_\{j\}\)\\cdot\\mathbf\{1\}\\big\[\\,\\Pi\(r\_\{i\}\)\\neq\\Pi\(r\_\{j\}\)\\,\\big\],\(2\)subject to a balance constraint that prevents one silo from absorbing most relations\.

We approximate Equation[2](https://arxiv.org/html/2609.13664#S3.E2)with a greedy weighted\-clustering heuristic, which suits the vocabulary sizes in this setting, where\|R\|<20\|R\|<20\. Relations are processed in descending order of total incident co\-occurrence weight\. Each is then placed in the silo maximizing the sum of edge weights to relations already assigned there\. Balance is controlled by a slack parameterϵ\\epsilon\. A silo may hold at most⌊ϵ​\|R\|/K⌋\\lfloor\\epsilon\\,\|R\|/K\\rfloorrelations, a cap relaxed only once every silo has reached it\. We setϵ=1\.25\\epsilon=1\.25, permitting25%25\\%more than the even share\. Ties are broken toward the less populated silo, which also places relations carrying no co\-occurrence weight\. Enrichment\-derived relations are treated as independent nodes\. The partitioner may therefore separate them from their base relations when the workload does not chain them\. BecauseΠcut\\Pi\_\{\\mathrm\{cut\}\}optimizes locality rather than size, it may accept more imbalance thanΠfreq\\Pi\_\{\\mathrm\{freq\}\}\. OnlyΠcut\\Pi\_\{\\mathrm\{cut\}\}consults the query workload, and it does so through aggregate co\-occurrence counts over training paths\.

### 3\.5Random Partitioning \(Πrand\\Pi\_\{\\mathrm\{rand\}\}\)

Relations are assigned to silos uniformly at random\. This strategy optimizes nothing and serves as the reference point against which the other three are measured, since a strategy that cannot beatΠrand\\Pi\_\{\\mathrm\{rand\}\}on the metric it targets is not earning its complexity\. A single random draw may happen to be favorable or unfavorable\. We therefore runΠrand\\Pi\_\{\\mathrm\{rand\}\}with twenty seeds for the structural metrics and three for the metrics that require training, and report the mean across them\. Together the four strategies span the design space, from the inherited default through the balance\-optimal and locality\-optimal extremes to an assignment that optimizes neither\.

![Refer to caption](https://arxiv.org/html/2609.13664v1/Figure2.png)Figure 3:Vertical partitioning as a data\-management decision\. A strategyΠ\\Piassigns each relation to one ofKKsilos\. The resulting layout is trained on a fixed substrate and characterized along five cost metrics \(M1–M5\) forK∈\{3,5,7\}K\\in\\\{3,5,7\\\}, so that, within eachKK, differences reflect the partition\.
### 3\.6Computing the Partitions

All four assignments are computed offline, once, before any training\.Πrand\\Pi\_\{\\mathrm\{rand\}\}andΠdom\\Pi\_\{\\mathrm\{dom\}\}areO⁡\(\|R\|\)O\(\|R\|\),Πfreq\\Pi\_\{\\mathrm\{freq\}\}isO⁡\(\|R\|​log⁡\|R\|\)O\(\|R\|\\log\|R\|\), andΠcut\\Pi\_\{\\mathrm\{cut\}\}requires one pass over the training paths followed by a balancedKK\-way cut over\|R\|\|R\|nodes\. Since relation vocabularies are small, partitioning is a one\-time cost negligible against the recurring costs of Section[4](https://arxiv.org/html/2609.13664#S4), and we exclude it from the comparisons\.

## 4Cost Metrics and Methodology

We characterize each partition along five data\-management metrics, measured on a fixed federated question answering substrate \(Figure[4](https://arxiv.org/html/2609.13664#S4.F4)\)\. Holding the substrate constant is what lets us attribute every difference to the partition alone\. Lower is better for all five metrics\. Table[1](https://arxiv.org/html/2609.13664#S4.T1)summarizes the five metrics, the units in which each is reported, and whether it varies with the partition\.

Table 1:The five cost metrics, the units in which each is reported, and whether it varies with the partition\. M3 and M4 are the two axes a partition trades off\. The other three are fixed by the graph, the substrate, and the silo count\.IDNameReported asDefinitionDepends onΠ\\Pi?M1Communication costGB per roundEq\.[3](https://arxiv.org/html/2609.13664#S4.E3)NoM2Candidate set and index sizeEntries per topic entityEq\.[4](https://arxiv.org/html/2609.13664#S4.E4)NoM3Cross\-silo path lengthCrossing rate per queryEq\.[5](https://arxiv.org/html/2609.13664#S4.E5)YesM4Load balanceImbalance, CV of silo sizesEq\.[6](https://arxiv.org/html/2609.13664#S4.E6)YesM5Query latencyMean ms per question—NoThe fixed substrate\.Every strategy is evaluated on the same pipeline, summarized in Figure[4](https://arxiv.org/html/2609.13664#S4.F4)and held constant across all experiments\. Each siloSkS\_\{k\}trains a local knowledge graph embedding on its own triplesTkT\_\{k\}using TransE[Bordes et al\. \(2013\)](https://arxiv.org/html/2609.13664#bib.bib10), and uploads only its entity embedding matrix to a server; raw triples and relation embeddings never leave the silo\. The server fuses the per\-silo entity embeddings into a joint representation\. A natural language question is encoded by a frozen BERT encoder[Devlin et al\. \(2019\)](https://arxiv.org/html/2609.13664#bib.bib11)followed by a trainable projection, anchored at the topic entity, and used to score candidate answers by similarity in the joint space\. At eachKK, the partition is therefore the only independent variable, and the co\-occurrence statistics needed byΠcut\\Pi\_\{\\mathrm\{cut\}\}are the only workload information any component reads\.

M1: Communication cost\.Federated training proceeds in rounds\. Each round, every silo uploads its entity embedding matrix and receives a gradient slice in return, so the per\-round volume is

Cround=K⋅\|E\|⋅d⋅2⋅4​bytes,Ctotal=T⋅Cround,C\_\{\\mathrm\{round\}\}=K\\cdot\|E\|\\cdot d\\cdot 2\\cdot 4\\text\{ bytes\},\\qquad C\_\{\\mathrm\{total\}\}=T\\cdot C\_\{\\mathrm\{round\}\},\(3\)where\|E\|\|E\|is the shared entity count,ddthe embedding dimension, the factor22covers upload and returned gradient, and44the bytes per float\.CroundC\_\{\\mathrm\{round\}\}is therefore identical for every partition at a givenKK, and we report it as M1\.CtotalC\_\{\\mathrm\{total\}\}also depends onTT, the rounds needed to reach the validation\-quality target\. M1 measures training\-time communication only; inference contacts no silo in the evaluated substrate; M3 is therefore reported as a structural locality measure rather than as measured inference communication\. It estimates the fragmentation that a partition would impose on systems that execute relation\-local reasoning across owners\.

![Refer to caption](https://arxiv.org/html/2609.13664v1/Figure3.png)Figure 4:The fixed federated question\-answering substrate used in all experiments\. Each silo trains a local TransE model and uploads entity embeddings\. The server fuses them, anchors the question at the topic entity, and scores candidates over a two\-hop set\. Dashed annotations mark where each cost metric \(M1–M5\) is incurred\.M2: Candidate set and index size\.To answer a question without traversing the graph at query time, the substrate precomputes, for each topic entitye0e\_\{0\}, a set of candidate answer entities reachable within two hops\. A two\-hop chain may have its first hop in one silo and its second in another\. The candidate set is therefore computed over the pooled neighborhood across silos, since expanding each silo independently and taking the union would miss exactly the cross\-silo chains this setting is defined by\. We report its mean size,

IndexSize=1\|Etopic\|​∑e0∈Etopic\|C⁡\(e0\)\|,\\mathrm\{IndexSize\}=\\frac\{1\}\{\|E\_\{\\mathrm\{topic\}\}\|\}\\sum\_\{e\_\{0\}\\in E\_\{\\mathrm\{topic\}\}\}\\big\|C\(e\_\{0\}\)\\big\|,\(4\)whereC⁡\(e0\)C\(e\_\{0\}\)is the pooled two\-hop candidate set ofe0e\_\{0\}\. This set depends on the graph rather than onΠ\\Pi, making it a control that confirms every strategy ranks over an equivalent candidate pool\.

M3: Cross\-silo path length\.Cross\-silo path length \(CSPL\) is the direct measure of locality\. For each query, its reasoning path is a sequence of relationsr1,r2,…r\_\{1\},r\_\{2\},\\dots, and a hop crosses a silo boundary whenever two consecutive relations are assigned to different silos\. We report the mean number of such crossings per query,

CSPL=1\|Q\|∑q∈Q∑i𝟏\[Π\(ri\)≠Π\(ri\+1\)\]\.\\mathrm\{CSPL\}=\\frac\{1\}\{\|Q\|\}\\sum\_\{q\\in Q\}\\sum\_\{i\}\\mathbf\{1\}\\big\[\\,\\Pi\(r\_\{i\}\)\\neq\\Pi\(r\_\{i\+1\}\)\\,\\big\]\.\(5\)A path spanning two relations contains one transition, contributing00when both relations lie in the same silo and11otherwise\. CSPL counts crossings per query and is bounded by 1 on two\-hop workloads, so its value equals the fraction of queries that cross a boundary, and we report it as a crossing rate throughout\. Enrichment creates direct relations between entities originally two hops apart, so recovery returns a single\-relation path for 37\.9% of MetaQA and 36\.7% of PathQuestion questions; these contain no transition and contribute zero\. CSPL is computed over all recovered paths\. A cross\-silo hop is the structural analogue of a distributed join\. Minimizing CSPL is the objective ofΠcut\\Pi\_\{\\mathrm\{cut\}\}\(Equation[2](https://arxiv.org/html/2609.13664#S3.E2)\), which builds its co\-occurrence graph from the same relation pairs this metric counts\.

M4: Load balance\.Federation proceeds in synchronized rounds, so the heaviest silo bounds each round and an unbalanced partition wastes the capacity of the lighter ones\. We quantify imbalance as the coefficient of variation \(CV\) of the per\-silo triple counts,

Imbalance=σ⁡\(\{\|Tk\|\}k=1K\)μ⁡\(\{\|Tk\|\}k=1K\),\\mathrm\{Imbalance\}=\\frac\{\\sigma\\big\(\\\{\|T\_\{k\}\|\\\}\_\{k=1\}^\{K\}\\big\)\}\{\\mu\\big\(\\\{\|T\_\{k\}\|\\\}\_\{k=1\}^\{K\}\\big\)\},\(6\)whereμ\\muandσ\\sigmaare the mean and standard deviation of the silo sizes\. M4 is reported as imbalance rather than balance so that lower is better for all five metrics\. This is the metricΠfreq\\Pi\_\{\\mathrm\{freq\}\}is designed to minimize\. Where the relation budget per silo is generous, it stands in opposition to CSPL\.

M5: Query latency\.Query latency is the end\-to\-end time to answer a single question, comprising candidate lookup, question encoding, topic anchoring, and scoring\. We report mean query latency\. Latency is downstream of M2, so it should not vary with the partition beyond measurement noise\.

Two families of cost\.Only M3 and M4 are consequences of the partition\. M2 and M5 are determined by the graph and the substrate\. Pooled candidate construction makes the scored set independent ofΠ\\Piby design, and latency is downstream of it\. M1, the per\-round volume of Equation[3](https://arxiv.org/html/2609.13664#S4.E3), is fixed by the silo count\. Total bytes also depend on the round countTT, which varies across training runs \(Section[6](https://arxiv.org/html/2609.13664#S6)\)\. We therefore verify M1, M2, and M5 as invariants and treat partitioning as a two\-axis problem in locality and balance\. How far those axes pull apart is what the study measures\.

## 5Experimental Setup

Datasets\.We evaluate on two multi\-hop knowledge graph question answering benchmarks that differ in domain, in graph density, and in the size of the relation vocabulary being partitioned\. MetaQA[Zhang et al\. \(2018\)](https://arxiv.org/html/2609.13664#bib.bib12)is a movie domain benchmark built over a WikiMovies knowledge base, with questions at one, two, and three hops; we use the two\-hop split\. PathQuestion[Zhou et al\. \(2018\)](https://arxiv.org/html/2609.13664#bib.bib13)is a person\-centric benchmark derived from Freebase, covering family, demographic, and biographical relations; we use its two\-hop split\. Both graphs are enriched offline with inverse and property chain axioms before partitioning, so that answer entities are reachable from the topic entity within the two\-hop expansion the substrate performs\. This enrichment is applied identically in every experimental cell and therefore does not confound the comparison\. It also expands the relation vocabulary that is subsequently partitioned: MetaQA grows from nine original relations to fifteen, while PathQuestion remains at thirteen relations, since its enrichment materializes inverse triples under existing relation names\.

Table[2](https://arxiv.org/html/2609.13664#S5.T2)summarizes the statistics that interact with partitioning\. The relation count determines the size of the design space, while the entity count drives per\-round communication and index size\. The two benchmarks stress different parts of the cost model\. PathQuestion has a larger entity space but fewer triples, so it is the sparser graph, whereas MetaQA is denser over fewer entities\.

Table 2:Benchmark statistics relevant to partitioning\. The relation count is the size of the set being partitioned\. The entity count drives communication volume and index size\.DatasetEntitiesRelationsTriplesDomainMetaQA43,23515405,433moviePathQuestion75,04313376,847person\-centricFixed learning substrate\.Because this is a study of partitioning, the learning model is held constant\. We fix TransE[Bordes et al\. \(2013\)](https://arxiv.org/html/2609.13664#bib.bib10)as the knowledge graph embedding and a frozen BERT[Devlin et al\. \(2019\)](https://arxiv.org/html/2609.13664#bib.bib11)question encoder with a small trainable projection head\. TransE keeps candidate scoring inexpensive and is a stable, widely used baseline\. Fixing this pair isolates the effect of the partition, so any difference in the five metrics is attributable toΠ\\Pi\. We therefore do not sweep alternative embeddings or encoders\.

Training configuration\.Every cell uses the same training configuration\. Local TransE models use 256\-dimensional embeddings trained with a margin ranking loss, margin1\.01\.0, ten negative samples per triple, Adam with learning rate10−310^\{\-3\}, and batch size512512\. On the server, the BERT encoder is frozen and only a two\-layer projection head is trained, using Adam with learning rate10−410^\{\-4\}, batch size6464, and margin1\.01\.0\. Gradient norms are clipped to1\.01\.0, and entity embeddings are renormalized to the unit sphere after each update\. Candidate construction expands two hops from each topic entity, with neighbor caps of5050at the first hop and2020at the second, and at most100100neighbors retained per entity\. The only quantities that change across cells are the partitionΠ\\Piand the silo countKK\.

Partitions and silo counts\.We apply each of the four strategiesΠdom\\Pi\_\{\\mathrm\{dom\}\},Πfreq\\Pi\_\{\\mathrm\{freq\}\},Πcut\\Pi\_\{\\mathrm\{cut\}\}, andΠrand\\Pi\_\{\\mathrm\{rand\}\}atK∈\{3,5,7\}K\\in\\\{3,5,7\\\}silos\. Each relation is assigned to exactly one silo, and the entity space is shared across all silos\.Πrand\\Pi\_\{\\mathrm\{rand\}\}is averaged over twenty seeds for the structural metrics M3 and M4, which require no training, and over three seeds for the quality control and total communication to target, which each require a full training run\. This yields a matrix of four strategies by three silo counts for each dataset\.

Recovering reasoning paths\.Both benchmarks provide a question, a topic entity, and an answer entity\. Neither annotates the relations traversed between them\. Since M3 and the co\-occurrence graph ofΠcut\\Pi\_\{\\mathrm\{cut\}\}are both defined over relation sequences, we recover a reasoning path for each question by breadth\-first search over the global graph, taking the shortest path from topic entity to answer\. Reverse traversals are normalized to their base relation, so the co\-occurrence graph, the partition, and the cross\-silo path length metric all use the same relation identities\. Recovery runs separately on the training and testing splits\.Πcut\\Pi\_\{\\mathrm\{cut\}\}consults only training paths, through aggregate co\-occurrence counts, while M3 is measured over held\-out test paths the partitioner never sees\. Recovery yields aggregate counts, so no individual query needs to leave a silo\. When several distinct paths connect a topic entity to an answer, the shortest is a proxy for the intended reasoning chain, which is a limitation of the analysis\.

Protocol\.For each combination of dataset, strategy, and silo count, we build the partition, construct the candidate index offline, train the fixed substrate, and record M1 through M5\. The quality target is Hits@3 on the validation split, set per dataset to reflect the achievable ceiling:0\.700\.70on MetaQA and0\.550\.55on PathQuestion, whose smaller training set supports a lower one\. Training runs for 40 rounds on MetaQA and 100 on PathQuestion, and the round first crossing the target definesTTin Equation[3](https://arxiv.org/html/2609.13664#S4.E3)\. Most cells clear the target early, so differences inTTare small and may reflect run\-to\-run variation\. Quality serves as a control rather than a result we claim\. All measurements use a single NVIDIA H100 GPU\.

Reproducibility\.The partitioning algorithms, the candidate index construction, and the measurement harness are independent of the learning substrate, so the characterization can be reproduced111Code:[https://github\.com/brains\-group/vertical\-fkg\-partitioning](https://github.com/brains-group/vertical-fkg-partitioning)with any embedding or encoder\. Each cell is determined by the dataset, the strategy, the silo count, and, forΠrand\\Pi\_\{\\mathrm\{rand\}\}, the random seed\.

## 6Results

Table[3](https://arxiv.org/html/2609.13664#S6.T3)reports the two metrics that differ across strategies, together with the quality control\. We first confirm comparable answer quality, then examine locality and balance\.

Table 3:Partitioning cost results for the two metrics that depend on the partition\. M3 is the cross\-silo path length of Equation[5](https://arxiv.org/html/2609.13664#S4.E5), reported as a crossing rate and measured on held\-out test paths\. M4 is the load balance metric of Equation[6](https://arxiv.org/html/2609.13664#S4.E6), reported as the coefficient of variation of per\-silo triple counts\. Lower is better for both\. Hits@3 on the test split is a quality control, not a result we claim\.Πrand\\Pi\_\{\\mathrm\{rand\}\}is averaged over twenty seeds for M3 and M4 and over three seeds for quality\. The best M3 and M4 value in each row is in bold\.MetaQAPathQuestionMetricKKΠdom\\Pi\_\{\\mathrm\{dom\}\}Πfreq\\Pi\_\{\\mathrm\{freq\}\}Πcut\\Pi\_\{\\mathrm\{cut\}\}Πrand\\Pi\_\{\\mathrm\{rand\}\}Πdom\\Pi\_\{\\mathrm\{dom\}\}Πfreq\\Pi\_\{\\mathrm\{freq\}\}Πcut\\Pi\_\{\\mathrm\{cut\}\}Πrand\\Pi\_\{\\mathrm\{rand\}\}M3: Cross\-silo pathlength \(crossing rate\)30\.0190\.0580\.0000\.0480\.5170\.3790\.2760\.39450\.0190\.0190\.0000\.0530\.5170\.4480\.5170\.47670\.0190\.0190\.0190\.0600\.5170\.5350\.5170\.503M4: Load balance\(imbalance, CV\)30\.3710\.0180\.3260\.4280\.6090\.0120\.1680\.32150\.9460\.3020\.6190\.6561\.1340\.0210\.6610\.51371\.2860\.5190\.5370\.7451\.4830\.2060\.4090\.560Quality control:Hits@330\.8140\.8560\.8280\.8410\.8000\.7280\.8310\.76450\.7990\.8170\.8160\.8110\.8000\.7540\.7280\.74070\.7960\.8100\.8010\.8080\.6610\.7740\.7490\.727Quality is matched on MetaQA, loosely on PathQuestion\.Cost comparisons are meaningful only at matched quality\. On MetaQA, Hits@3 spans0\.7960\.796to0\.8560\.856\. The spread at a fixedKKis at most 0\.042\. On PathQuestion it spans0\.6610\.661to0\.8310\.831\. The wider range reflects a much smaller training set of1,5241\{,\}524questions\. On PathQuestion, the other strategies change rank asKKchanges, whileΠrand\\Pi\_\{\\mathrm\{rand\}\}, averaged over three seeds, stays third at everyKK\. This is what we would expect if the wider spread reflects run\-to\-run variation on a small training set rather than the partition\. We therefore treat PathQuestion as loosely matched rather than matched, so cost comparisons on that benchmark should be read as approximate\. Quality is reported only to confirm that the strategies are comparable, not as a result we claim\.

Locality\.Crossing rates are measured on held\-out test paths, whileΠcut\\Pi\_\{\\mathrm\{cut\}\}builds its co\-occurrence graph from training paths only\. The numbers therefore reflect generalization to unseen queries rather than fit to the optimization target\. On MetaQA,Πcut\\Pi\_\{\\mathrm\{cut\}\}records0\.0000\.000atK=3K=3andK=5K=5, against0\.0190\.019forΠdom\\Pi\_\{\\mathrm\{dom\}\}and0\.0480\.048and0\.0530\.053forΠrand\\Pi\_\{\\mathrm\{rand\}\}, respectively, and ties for best atK=7K=7\. Absolute magnitudes are small there\. Every strategy stays at or below0\.060\.06, so partitioning has limited practical effect on locality for this benchmark\.

PathQuestion shows a much larger locality effect\. AtK=3K=3,Πcut\\Pi\_\{\\mathrm\{cut\}\}records0\.2760\.276against0\.5170\.517for the inherited partition, a reduction of47%47\\%\. The contrast sharpens on paths that contain a relation transition, where a crossing is possible at all\. Shortest\-path recovery returns a single\-relation path for36\.7%36\.7\\%of PathQuestion questions, leaving63\.3%63\.3\\%where transitions are possible\. Dividing by that fraction, the inherited partition crosses a boundary on82%82\\%of such queries andΠcut\\Pi\_\{\\mathrm\{cut\}\}on44%44\\%\. AtK=5K=5andK=7K=7,Πcut\\Pi\_\{\\mathrm\{cut\}\}no longer leads\. AsKKgrows, each silo holds fewer of the1313to1515relations, and the balance cap admits at most⌊1\.25​\|R\|/K⌋\\lfloor 1\.25\\,\|R\|/K\\rfloorrelations per silo\. AtK=7K=7this leaves room for two, too little freedom to co\-locate a chain\.Πdom\\Pi\_\{\\mathrm\{dom\}\}records the same crossing rate at everyKKon both benchmarks, because the partition itself does not change\. With three semantic domains, silos beyond the third receive no relations, and the relation\-to\-silo map is identical atK=3K=3,55, and77\.

Balance\.Πfreq\\Pi\_\{\\mathrm\{freq\}\}achieves the lowest imbalance in all six combinations of dataset and silo count\. AtK=3K=3it records 0\.018 on MetaQA and 0\.012 on PathQuestion, roughly twenty\-four and twenty\-seven times lower thanΠrand\\Pi\_\{\\mathrm\{rand\}\}\.Πdom\\Pi\_\{\\mathrm\{dom\}\}becomes the worst\-balanced strategy atK≥5K\\geq 5on both datasets and deteriorates sharply asKKgrows, from0\.3710\.371to1\.2861\.286on MetaQA and from0\.6090\.609to1\.4831\.483on PathQuestion\. The cause is again the empty surplus silos, which inflate the coefficient of variation, and it is a concrete limitation for practitioners scaling out an existing federation\. Figure[5](https://arxiv.org/html/2609.13664#S6.F5)shows both trends acrossKK\.

Two regimes rather than a universal trade\-off\.The relationship between locality and balance depends on the ratio of relations to silos\. AtK=3K=3, where each silo can hold several relations, the two objectives conflict directly\. On MetaQA,Πcut\\Pi\_\{\\mathrm\{cut\}\}attains the best crossing rate in the study,0\.0000\.000, but does so at0\.3260\.326imbalance\.Πfreq\\Pi\_\{\\mathrm\{freq\}\}attains the best imbalance,0\.0180\.018, at the highest crossing rate of any non\-random strategy,0\.0580\.058\. Neither dominates the other, and Figure[6](https://arxiv.org/html/2609.13664#S6.F6)shows no strategy in the lower\-left corner\.

At larger values ofKKthe pattern changes\. As the number of silos increases, each holds fewer of the1313to1515relations and the balance cap admits fewer co\-located pairs\. Locality differences collapse while imbalance differences persist\. On PathQuestion,Πfreq\\Pi\_\{\\mathrm\{freq\}\}is at least as good asΠcut\\Pi\_\{\\mathrm\{cut\}\}on*both*axes atK=5K=5; atK=7K=7it gives up0\.0180\.018on crossing rate while holding roughly half the imbalance\. The trade\-off therefore weakens asKKgrows\. Where the relation budget per silo is thin, balance\-aware partitioning is the safer choice because it retains a strong load\-balance advantage while remaining competitive on locality\.

Remaining metrics\.The other three metrics behave as the cost model predicts\. Candidate index size \(M2\) is constant across strategies, at144\.3144\.3entries per topic entity on MetaQA and103\.6103\.6on PathQuestion\. Pooled candidate construction makes the scored set depend on the graph rather than onΠ\\Pi, which confirms that all strategies rank over an equivalent pool\. Query latency \(M5\) is correspondingly comparable, averaging10\.510\.5ms on MetaQA and10\.010\.0ms on PathQuestion\. Per\-round communication \(M1\) follows Equation[3](https://arxiv.org/html/2609.13664#S4.E3)and is fixed by the silo count, at0\.270\.27,0\.440\.44, and0\.620\.62GB per round on MetaQA forK=3K=3,55, and77\. Total bytes to target depend on the round countTT, which varies across cells without a systematic pattern\. Across three training seeds ofΠrand\\Pi\_\{\\mathrm\{rand\}\}atK=5K=5, total bytes to target vary by a factor of two, a range as wide as that between strategies\. Differences in convergence are therefore within training variance, not a clear effect of the partition\. A partition should be chosen for locality or balance, not to reduce training bandwidth or query time\.

What is structural and what is measured\.Two of our observations follow from the setup rather than from data\. ThatΠdom\\Pi\_\{\\mathrm\{dom\}\}leaves silos empty onceKKexceeds the number of semantic domains is a property of the strategy, and that the balance cap admits at most⌊ϵ​\|R\|/K⌋\\lfloor\\epsilon\|R\|/K\\rfloorrelations per silo is arithmetic\. We report them because a practitioner scaling out an inherited federation will encounter them, not as findings\. What is measured is where the two axes fall for a given graph and workload\. The 47% reduction in crossing rate on PathQuestion atK=3K=3is empirical, as is the fact thatΠfreq\\Pi\_\{\\mathrm\{freq\}\}matchesΠcut\\Pi\_\{\\mathrm\{cut\}\}on locality atK=5K=5with roughly 31\-fold lower imbalance\. Neither is predictable from the framework\. The quantity that decides which regime holds is relations per silo,\|R\|/K\|R\|/K, not\|R\|\|R\|orKKalone\. Our benchmarks reach the thin regime atK=7K=7only because\|R\|\|R\|is small, and a federation with two hundred relations would reach it nearK=100K=100\. We expect the guidance to transfer by that ratio, but we have not verified it on a large vocabulary and mark this as the main open item\.

![Refer to caption](https://arxiv.org/html/2609.13664v1/fig_cost_curves.png)Figure 5:Cost metrics versus silo countKK\. Panels \(a,c\) show crossing rate \(M3\) and panels \(b,d\) load imbalance \(M4\); lower is better\. Crossing rates use held\-out test paths, andΠrand\\Pi\_\{\\mathrm\{rand\}\}is averaged over twenty seeds\.Πcut\\Pi\_\{\\mathrm\{cut\}\}leads on locality atK=3K=3, whileΠfreq\\Pi\_\{\\mathrm\{freq\}\}consistently minimizes imbalance\. Panels \(a\) and \(c\) use different vertical scales\.![Refer to caption](https://arxiv.org/html/2609.13664v1/fig_tradeoff.png)Figure 6:Locality against balance atK=3K=3, where the trade\-off is sharpest\. Dashed lines mark the best value achieved on each axis, and no strategy reaches their intersection\.Πcut\\Pi\_\{\\mathrm\{cut\}\}is lowest on crossing rate andΠfreq\\Pi\_\{\\mathrm\{freq\}\}is leftmost on imbalance, and no strategy is best on both axes\. AtK≥5K\\geq 5the opposition weakens \(Figure[5](https://arxiv.org/html/2609.13664#S6.F5)\)\.
## 7Conclusion

We treated the vertical partition as an object of study rather than a fixed input, formalizing the relation\-to\-silo assignment as a design space and defining five cost metrics\. Three proved to be invariants of the graph and the silo count, leaving locality and balance as the axes a partition trades off\. Locality\-aware partitioning works where the relation budget allows it: atK=3K=3on PathQuestion,Πcut\\Pi\_\{\\mathrm\{cut\}\}cuts the crossing rate from0\.5170\.517to0\.2760\.276\. Balance\-aware partitioning works reliably, withΠfreq\\Pi\_\{\\mathrm\{freq\}\}lowest on imbalance in every cell\. The conflict is strongest at low silo counts and weakens asKKgrows; once each silo holds too few relations to co\-locate a chain,Πfreq\\Pi\_\{\\mathrm\{freq\}\}becomes competitive on locality while keeping its advantage on balance\. Guidance is conditional\. Federations with room to co\-locate reasoning paths should favorΠcut\\Pi\_\{\\mathrm\{cut\}\}; those bounded by their slowest silo, or spread across many silos, should favorΠfreq\\Pi\_\{\\mathrm\{freq\}\}\. An inherited partition sits far from both optima and does not populate more silos than there are semantic domains\. Three limitations bound these claims\. Our benchmarks have fewer than twenty relation types, so the thin regime arrives atK=7K=7\. Since the governing quantity is relations per silo, we expect the same two regimes at proportionally larger silo counts on a large vocabulary, but this remains a conjecture\.Πcut\\Pi\_\{\\mathrm\{cut\}\}also uses a greedy heuristic over recovered rather than annotated paths, which biases M3 and the method it evaluates in the same direction\. Finally, we characterize four heuristics rather than optimizing the trade\-off directly; a partitioner minimizing a weighted combination of cut weight and imbalance would trace the frontier between the two axes\. Larger vocabularies, a frontier partitioner, drifting workloads, and partial entity alignment are natural next steps\.

## Declaration on Generative AI

The authors used Claude \(Anthropic\) for language editing and structural refinement\. All content was reviewed by the authors, who take responsibility for the submission\. No generative AI was used to produce research findings, experimental results, or citations\. This complies with CEUR’s Policy on AI\-Assisting Tools\.

## References

- Abadiet al\.\(2009\)D\. J\. Abadi, A\. Marcus, S\. R\. Madden, and K\. HollenbachSW\-Store: a vertically partitioned DBMS for Semantic Web data management\.The VLDB Journal18\(2\),pp\. 385–406\.Cited by:[§2\.1](https://arxiv.org/html/2609.13664#S2.SS1.p1.1)\.
- Akhteret al\.\(2018\)A\. Akhter, A\. Ngomo Ngonga, and M\. SaleemAn empirical evaluation of RDF graph partitioning techniques\.InEuropean Knowledge Acquisition Workshop,pp\. 3–18\.Cited by:[§2\.1](https://arxiv.org/html/2609.13664#S2.SS1.p1.1)\.
- Aliet al\.\(2022\)W\. Ali, M\. Saleem, B\. Yao, A\. Hogan, and A\. N\. NgomoA survey of RDF stores and SPARQL engines for querying knowledge graphs\.The VLDB Journal31\(3\),pp\. 1–26\.Cited by:[§2\.1](https://arxiv.org/html/2609.13664#S2.SS1.p1.1)\.
- Bappy and Seneviratne \(2026\)M\. S\. I\. K\. Bappy and O\. SeneviratneFedV\-KGQA: multi\-hop question answering over vertically partitioned knowledge graphs\.arXiv preprint arXiv:2608\.24846\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p2.1)\.
- Bordeset al\.\(2013\)A\. Bordes, N\. Usunier, A\. Garcia\-Duran, J\. Weston, and O\. YakhnenkoTranslating embeddings for modeling multi\-relational data\.Advances in neural information processing systems26\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.SS0.SSS0.Px1.p3.1),[§4](https://arxiv.org/html/2609.13664#S4.p2.1),[§5](https://arxiv.org/html/2609.13664#S5.p3.1)\.
- Çatalyüreket al\.\(2023\)Ü\. Çatalyürek, K\. Devine, M\. Faraj, L\. Gottesbüren, T\. Heuer, H\. Meyerhenke, P\. Sanders, S\. Schlag, C\. Schulz, D\. Seemaier,et al\.More recent advances in \(hyper\)graph partitioning\.ACM Computing Surveys55\(12\),pp\. 1–38\.Cited by:[§2\.1](https://arxiv.org/html/2609.13664#S2.SS1.p1.1)\.
- Chenet al\.\(2024a\)D\. Chen, H\. Zhu, J\. Gu, R\. Chen, and M\. XieUnaligned federated knowledge graph embedding\.InInternational Semantic Web Conference,pp\. 180–198\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.p1.1)\.
- Chenet al\.\(2021\)M\. Chen, W\. Zhang, Z\. Yuan, Y\. Jia, and H\. ChenFedE: embedding knowledge graphs in federated setting\.InProceedings of the 10th international joint conference on knowledge graphs,pp\. 80–88\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Chenet al\.\(2024b\)R\. Chen, W\. Jiang, C\. Qin, I\. S\. Rawal, C\. Tan, D\. Choi, B\. Xiong, and B\. AiLLM\-based multi\-hop question answering with knowledge graph integration in evolving environments\.InFindings of the Association for Computational Linguistics: EMNLP 2024,pp\. 14438–14451\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p2.1)\.
- Devlinet al\.\(2019\)J\. Devlin, M\. Chang, K\. Lee, and K\. ToutanovaBERT: pre\-training of deep bidirectional transformers for language understanding\.InProceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 \(long and short papers\),pp\. 4171–4186\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.SS0.SSS0.Px1.p3.1),[§4](https://arxiv.org/html/2609.13664#S4.p2.1),[§5](https://arxiv.org/html/2609.13664#S5.p3.1)\.
- Fanet al\.\(2023\)W\. Fan, R\. Xu, Q\. Yin, W\. Yu, and J\. ZhouApplication\-driven graph partitioning\.The VLDB Journal32\(1\),pp\. 149–172\.Cited by:[§2\.1](https://arxiv.org/html/2609.13664#S2.SS1.p1.1)\.
- Guntiet al\.\(2025\)A\. Gunti, A\. Patil, A\. Narayan, A\. Gulati, and B\. DasA federated learning approach for question and answering on knowledge graphs\.J\. Inf\. Syst\. Eng\. Manage\.10\(30\),pp\. 704–711\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.p1.1)\.
- Huet al\.\(2025\)Q\. Hu, W\. Jiang, H\. Li, Z\. Wang, J\. Bai, Q\. Mao, Y\. Song, L\. Fan, and J\. LiLearning federated neural graph databases for answering complex queries from distributed knowledge graphs\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=3K1LRetR6Y)Cited by:[§1](https://arxiv.org/html/2609.13664#S1.p1.1)\.
- Huet al\.\(2023\)Y\. Hu, W\. Liang, R\. Wu, K\. Xiao, W\. Wang, X\. Li, J\. Liu, and Z\. QinQuantifying and defending against privacy threats on federated knowledge graph embedding\.InProceedings of the ACM Web Conference 2023,pp\. 2306–2317\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Jianget al\.\(2026\)W\. Jiang, K\. Liang, W\. Huang, X\. Zhang, Z\. Xu, G\. Wan, C\. Tan, F\. X\. Fan, and J\. WangUnveiling and mitigating untargeted poisoning attacks on federated knowledge graph embedding\.InProceedings of the ACM Web Conference 2026,pp\. 2569–2580\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Khanet al\.\(2024\)M\. S\. I\. Khan, A\. Gupta, O\. Seneviratne, and S\. PattersonFed\-RD: privacy\-preserving federated learning for financial crime detection\.In2024 IEEE Symposium on Computational Intelligence for Financial Engineering and Economics \(CIFEr\),pp\. 1–9\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Liet al\.\(2025\)X\. Li, Y\. Zhu, B\. Pang, G\. Yan, Y\. Yan, Z\. Li, Z\. Wu, W\. Zhang, R\. Li, and G\. WangOpenFGL: a comprehensive benchmark for federated graph learning\.Proc\. VLDB Endow\.18\(5\),pp\. 1305–1320\.External Links:ISSN 2150\-8097,[Link](https://doi.org/10.14778/3718057.3718061),[Document](https://dx.doi.org/10.14778/3718057.3718061)Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Luoet al\.\(2024\)L\. Luo, Y\. Li, R\. Haffari, and S\. PanReasoning on graphs: faithful and interpretable large language model reasoning\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 14400–14423\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p2.1)\.
- Maet al\.\(2025\)C\. Ma, Y\. Chen, T\. Wu, A\. Khan, and H\. WangLarge language models meet knowledge graphs for question answering: synthesis and opportunities\.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing,pp\. 24589–24608\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p2.1)\.
- Saxenaet al\.\(2020\)A\. Saxena, A\. Tripathi, and P\. TalukdarImproving multi\-hop question answering over knowledge graphs using knowledge base embeddings\.InProceedings of the 58th annual meeting of the association for computational linguistics,pp\. 4498–4507\.Cited by:[§1](https://arxiv.org/html/2609.13664#S1.p2.1),[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p2.1)\.
- Sunet al\.\(2024\)J\. Sun, C\. Xu, L\. Tang, S\. Wang, C\. Lin, Y\. Gong, L\. Ni, H\. Shum, and J\. GuoThink\-on\-graph: deep and responsible reasoning of large language model on knowledge graph\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 3868–3898\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p2.1)\.
- Tranet al\.\(2024\)L\. Tran, S\. Chari, M\. S\. I\. Khan, A\. Zachariah, S\. Patterson, and O\. SeneviratneA differentially private blockchain\-based approach for vertical federated learning\.In2024 IEEE International Conference on Decentralized Applications and Infrastructures \(DAPPS\),pp\. 86–92\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Zhanget al\.\(2024\)X\. Zhang, Z\. Zeng, X\. Zhou, and C\. MiaoLow\-dimensional federated knowledge graph embedding via knowledge distillation\.arXiv preprint arXiv:2408\.05748\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Zhanget al\.\(2025\)X\. Zhang, Z\. Zeng, X\. Zhou, D\. Niyato, and Z\. ShenPersonalized federated knowledge graph embedding with client\-wise relation graph\.Applied Intelligence55\(5\),pp\. 318\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Zhanget al\.\(2018\)Y\. Zhang, H\. Dai, Z\. Kozareva, A\. Smola, and L\. SongVariational reasoning for question answering with knowledge graph\.InProceedings of the AAAI conference on artificial intelligence,Vol\.32\.Cited by:[§5](https://arxiv.org/html/2609.13664#S5.p1.1)\.
- Zhouet al\.\(2018\)M\. Zhou, M\. Huang, and X\. ZhuAn interpretable reasoning network for multi\-relation question answering\.InProceedings of the 27th international conference on computational linguistics,pp\. 2010–2022\.Cited by:[§5](https://arxiv.org/html/2609.13664#S5.p1.1)\.
- Zhuet al\.\(2023\)X\. Zhu, G\. Li, and W\. HuHeterogeneous federated knowledge graph embedding learning and unlearning\.InProceedings of the ACM web conference 2023,pp\. 2444–2454\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.
- Zhuet al\.\(2025\)X\. Zhu, Y\. Xie, Y\. Liu, Y\. Li, and W\. HuParameter\-efficient federated knowledge graph embedding learning and unlearning\.InInternational Semantic Web Conference,pp\. 462–480\.Cited by:[§2\.2](https://arxiv.org/html/2609.13664#S2.SS2.p1.1)\.