垂直分区的联邦知识图谱成本特性分析

# 垂直分区联邦知识图谱的成本特征
来源: https://arxiv.org/html/2609.13664
###### 摘要

知识图谱日益分布在自主组织之间，这些组织共享一个实体空间但拥有不相交的子关系集，形成了垂直分区。回答一个多跳查询可能需要结合来自多个数据仓库的事实，这使得分区策略成为影响通信、索引、负载均衡和查询延迟的关键数据管理决策。然而，与不同分区策略相关的成本尚未得到充分研究。我们将垂直分区形式化为一个设计空间，并比较了四种策略：语义领域分组、频率平衡分区、共现图切割分区和随机分区。我们使用五个指标评估它们：通信成本、候选索引大小、跨仓库路径长度、负载平衡和端到端查询延迟。其中三个指标被证明由图本身和仓库数量决定，而非由分区决定，这将设计问题简化为两个相互冲突的维度：跨仓库路径长度和负载平衡。在MetaQA和PathQuestion上的实验使用了一个固定的联邦知识图谱问答架构，该架构基于TransE嵌入和冻结的BERT编码器，并跨三种仓库配置进行测试。通过保持学习模型不变，我们隔离了分区的影响，并表明局部性与平衡之间的权衡仅在每个仓库可以容纳多个关系时成立，随着仓库数量的增加而减弱。该研究为受跨仓库推理或仓库负载约束的部署提供了实践指导。

###### 关键词

联邦知识图谱，垂直分区，联邦问答，数据管理成本分析，图分区

††copyrightyear:2026††copyright:本文版权归其作者所有。允许在知识共享署名4.0国际许可协议（CC BY 4.0）下使用。††venue:DMKG’26：第二届数据管理知识图谱国际研讨会，2026年10月，意大利巴里††email:islamm9@rpi\.edu††email:senevo@rpi\.edu††address:伦斯勒理工学院，美国纽约州特洛伊市12180

## 1引言

知识图谱网络并非单一的可查询存储，而是自主来源的生态系统。在许多实际部署中，关于相同实体的事实分布在组织之间，每个组织拥有关系词汇表的不同切片：一家电影制片厂记录谁导演了电影，一家流媒体平台记录谁出演了它，一项元数据服务记录其类型。这三者都描述了相同的实体，但没有任何一方拥有完整的图，并且由于治理、商业敏感性和数据主权限制，原始数据无法集中化。这是知识图谱的*垂直分区*：实体空间是共享的，而关系被分割为不相交的、私有的子集。这与大多数联邦知识图谱工作所研究的横向联邦Hu等人（2025） (https://arxiv.org/html/2609.13664#bib.bib25)；Gunti等人（2025） (https://arxiv.org/html/2609.13664#bib.bib24)；Chen等人（2024a） (https://arxiv.org/html/2609.13664#bib.bib5)有根本区别，在横向联邦中，每一方在不同实体上拥有相同的关系，并且通常可以在自己的分片内回答查询。

在垂直分区下，这种局部性丢失了。回答一个多跳查询意味着链接被设计为跨方分割的事实：一条推理路径可能始于一个仓库，经过一个共享实体，结束于另一个仓库。问题*“哪些演员出演了诺兰执导的电影？”*需要制片厂持有的导演关系和平台持有的表演关系，因此任何一方都无法单独回答它。每次跨越仓库边界的跳转所扮演的角色，相当于关系型联邦中的分布式连接，因为它迫使将两个所有者持有的证据结合起来（图1 (https://arxiv.org/html/2609.13664#S1.F1)）。回答此类问题的要素是分别存在的：基于嵌入的方法在集中式图上对多跳问题的答案进行排序Saxena等人（2020） (https://arxiv.org/html/2609.13664#bib.bib9)，而联邦嵌入方法学习跨方的表示而不共享原始三元组Chen等人（2021） (https://arxiv.org/html/2609.13664#bib.bib1)。最近的工作将它们结合起来，表明通过在每个仓库内训练本地嵌入并在服务器上融合，可以在垂直分区的图上实现多跳问答Bappy和Seneviratne（2026） (https://arxiv.org/html/2609.13664#bib.bib26)。然而，那一系列工作将分区视为固定输入，并专注于答案质量。

#### 关于每个仓库暴露内容的说明：

本文的术语源自数据管理，“分布式连接”和“跨仓库跳转”等术语描述的是工作负载的形状，而非服务机制。在我们的设定中，没有仓库暴露查询端点，也没有仓库在其自身的三元组上评估子查询。一个仓库仅释放派生量，在这里是本地实体嵌入矩阵。一个问题通过在融合嵌入空间中对候选实体进行排序来回答，而不是通过规划和执行分布式查询。正是这一约束使得将关系分配给仓库成为一个具有真实后果的物理设计决策。没有运行时优化器可以重新排序、下推或缓存来绕过糟糕的布局，因此分区在跨仓库推理方面的成本会在每个查询上付出。

一个先前同样实际的问题在很大程度上被忽视了：给定一个关系词汇表和一组仓库，*应如何将关系分配给仓库，以及每种分配会产生哪些存储和查询成本？*这完全是一个数据管理问题。它涉及分区、索引、联邦查询处理以及联邦带来的通信，其答案并非表面文章。将紧密共同使用的关系放在同一个仓库中，可以缩短查询必须遍历的跨仓库路径，但可能导致仓库大小严重失衡，从而使一个过载的仓库成为每个同步轮次的瓶颈。均匀地分布关系可以平衡负载，但会分离经常被链接的关系，从而延长跨仓库路径。在一个维度上表现良好的分区，在另一个维度上通常表现不佳，至少当每个仓库可以容纳多个关系时是如此，并且相同的工作负载服务成本可能因关系的划分方式而便宜或昂贵。这些正是从业者在部署联邦知识图谱时必须权衡的权衡，然而目前还没有系统的说明：今天的从业者选择一个分区，或者继承一个分区，却无法知道它的成本或它与最佳可实现状态的差距。

本文提供了这一特征描述。我们将分区视为研究对象，而非固定输入，将其形式化为将关系词汇表分配给仓库的问题，并定义了一个涵盖问题自然轴线的小策略空间：语义领域分组，反映组织通常继承的分区；频率平衡分区，使每个仓库持有的数据均衡；共现图切割分区，保持频繁链接的关系在一起以保持局部性；以及随机分区，它不优化任何东西，仅作为基线。我们沿着五个数据管理指标衡量每种策略的后果，即通信成本、候选索引大小、跨仓库路径长度、负载平衡和端到端查询延迟。其中三个被证明是图和仓库数量的不变量，使得局部性和平衡成为分区实际权衡的两个维度。至关重要的是，我们保持学习模型固定，在基于TransEBordes等人（2013） (https://arxiv.org/html/2609.13664#bib.bib10)和冻结BERT编码器Devlin等人（2019） (https://arxiv.org/html/2609.13664#bib.bib11)构建的相同联邦问答基板上评估每种策略，因此在每个仓库数量下，成本的任何差异都可归因于分区本身。我们的贡献如下。

- •将垂直分区视为设计空间。我们将垂直分区知识图谱的关系到仓库分配问题形式化，并定义了跨越空间自然轴线的四个具体策略。
- •数据管理成本模型。我们定义了五个可测量的成本指标，即每轮通信、候选集和索引大小、跨仓库路径长度、负载平衡和查询延迟。它们共同捕捉了分区存储和查询的成本。我们进一步证明，其中五个指标中的三个是图和仓库数量的不变量，而非分区的后果，因此分区决策简化为一个二维权衡。
- •实证特征描述。在两个基准测试和三种仓库数量下，保持学习模型固定，我们量化了每种策略所做的权衡，并提炼出哪种策略适合哪种部署目标的实用指导。

参见标题图1：垂直联邦设置中的多跳问答。仓库拥有共享实体空间E上的不相交关系子集，因此一个2跳问题可能跨仓库边界链接事实。

## 2相关工作

### 2\.1图数据的分区与物理设计

图数据集的布局方式决定了其查询成本，选择这种布局长期被视为核心数据管理决策。在RDF数据管理中，SW-StoreAbadi等人（2009） (https://arxiv.org/html/2609.13664#bib.bib6)引入了垂直分区存储，按谓词对三元组进行分组，以便仅涉及少数谓词的查询只需扫描少量数据。平衡图分区仍然是一个活跃的领域，最新的综述列举了底层机制的成熟度Çatalyürek等人（2023） (https://arxiv.org/html/2609.13664#bib.bib15)；Ali等人（2022） (https://arxiv.org/html/2609.13664#bib.bib7)，而系统工作继续在大规模上提高分区质量，例如同时减少边切割和工作负载不平衡的流式分区器。与我们的局部性导向策略最相似的是应用驱动分区Fan等人（2023） (https://arxiv.org/html/2609.13664#bib.bib14)，它从将运行在其上的工作负载而非仅从图拓扑中选择布局。RDF分区策略的实证比较Akhter等人（2018） (https://arxiv.org/html/2609.13664#bib.bib8)证实了我们研究的反复出现的紧张关系：为平衡存储而进行的分区往往会切断查询遍历的连接路径，因此最小化不平衡的布局很少是使跨分区流量最小化的布局，没有单一方案是普遍最优的。

我们的工作采用了这种物理设计视角，但在两个先前分区工作未结合的轴线上有所不同。首先，查询是一个通过基于嵌入的排序回答的*自然语言多跳问题*，而不是具有显式计划的结构化查询。因此，分区的成本由学习的检索管道（即本地嵌入、服务器端融合和候选排序）中介，而非关系运算符树，并通过该管道构建的结构（如每个仓库的候选索引）实现。其次，分区边界与*所有权和隐私*边界重合：关系由自主组织持有，原始三元组不能跨越仓库，跨分区连接是参与方之间的一轮联邦通信，他们从不暴露其数据，而非集群内洗牌。这些共同改变了分区成本和哪些分区是可接受的。据我们所知，在这些条件下，替代的关系到仓库分配的成本尚未被表征，这正是本文要解决的空白。

### 2\.2联邦知识图谱与问答

另外两条工作线提供了我们测量这些成本的基板，但都没有研究分区问题本身。联邦知识图谱嵌入学习跨方的表示而不共享原始数据，但几乎完全在*横向*设置中，其中各方在不同实体上拥有相同的关系，并且查询通常可以在单个分片内回答。FedEChen等人（2021） (https://arxiv.org/html/2609.13664#bib.bib1)建立了通过服务器聚合实体嵌入的模式，此后该领域发展迅速，针对异质性和遗忘Zhu等人（2023） (https://arxiv.org/html/2609.13664#bib.bib2)；Zhu等人（2025） (https://arxiv.org/html/2609.13664#bib.bib16)、更便宜的嵌入交换Zhang等人（2024） (https://arxiv.org/html/2609.13664#bib.bib4)、个性化Zhang等人（2025） (https://arxiv.org/html/2609.13664#bib.bib19)以及重复交换带来的隐私和鲁棒性风险Hu等人（2023） (https://arxiv.org/html/2609.13664#bib.bib3)；Jiang等人（2026） (https://arxiv.org/html/2609.13664#bib.bib18)；基准测试也已成熟Li等人（2025） (https://arxiv.org/html/2609.13664#bib.bib17)。这一系列工作与我们共享联邦框架，但假设分区是给定的，并以模型质量或隐私为目标，而非分区本身的成本。垂直情况，即单条推理路径被设计为跨所有者分割的情况，仍然相对未被探索。垂直联邦在知识图谱之外已被研究，其中各方在共享样本上持有不相交的特征集Tran等人（2024） (https://arxiv.org/html/2609.13664#bib.bib28)，联邦学习在更广泛领域用于因监管原因无法集中数据的情况Khan等人（2024） (https://arxiv.org/html/2609.13664#bib.bib27)。在这两种情况下，被分割的对象是特征而非关系，因此没有推理路径跨越边界。

知识图谱上的问答同样取得了进展。基于嵌入的方法在学习的空间中对候选答案进行评分，如EmbedKGQASaxena等人（2020） (https://arxiv.org/html/2609.13664#bib.bib9)，而最近的工作将大型语言模型与图遍历相结合，通过代理探索、检索的关系路径或对演化图的多跳推理Sun等人（2024） (https://arxiv.org/html/2609.13664#bib.bib20)；Luo等人（2024） (https://arxiv.org/html/2609.13664#bib.bib21)；Chen等人（2024b） (https://arxiv.org/html/2609.13664#bib.bib22)；Ma等人（2025） (https://arxiv.org/html/2609.13664#bib.bib23)。这些方法假设集中式图访问或集中可用的检索证据。一条较小的研究线将问答扩展到垂直分区的联邦图，证明可以在不集中图的情况下恢复多跳答案Bappy和Seneviratne（2026） (https://arxiv.org/html/2609.13664#bib.bib26)。那项工作确立了可行性并优化了答案质量；它没有询问底层分区应如何选择或不同分区存储和查询的成本是多少。我们将这样一个管道视为*固定*的基板并保持不变，因此我们报告的差异仅可归因于分区本身。因此，我们的关注点是正交和互补的：先前工作询问的是问题是否可以在给定的分区上回答，而我们询问的是分区应如何选择及其成本。

## 3垂直分区设计空间

### 3\.1问题设置与符号表示

设G=(E,R,T)G=(E,R,T)为一个知识图谱，其中实体集为E，关系集为R，三元组集T⊆E×R×ET\\subseteq E\\times R\\times E。一个*垂直分区*到K个仓库是