💻 computer science

COREKG: Coreset-Guided Personalized Summarization of Knowledge Graphs

本文介绍了COREKG，这是一个个性化知识图谱摘要框架，它利用核心集理论和基于敏感度的重要性采样，生成紧凑且用户特定的子图，与最先进的方法相比，在保持高准确性和结构覆盖度的同时显著降低了存储需求和查询运行时间。

原作者： Sohel Aman Khan, Raghava Mutharaju, Supratim Shit

发布于 2026-05-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Sohel Aman Khan, Raghava Mutharaju, Supratim Shit

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你拥有一个包含数十亿本书籍的庞大图书馆（这就是你的知识图谱）。它包罗万象：关于人物、地点、公司的各种事实，以及它们之间的关联。虽然这座图书馆令人惊叹，但它过于庞大，无法放进口袋随身携带；而且，如果你向图书管理员提出一个具体问题，他们可能会在浩如烟海的书籍中迷失方向，难以找到答案。

通常，图书管理员会尝试通过挑选最著名的书籍来制作整个图书馆的“摘要”。但这里有个问题：你可能只关心“19 世纪诗歌”方面的书籍，而你的邻居只关心“太空旅行”。为所有人提供单一的摘要过于笼统；这就像你想要诗歌，却得到了一本关于太空旅行的书。

这正是论文COREKG登场之处。它提出了一种新方法，为你创建一个个性化的微型图书馆。

核心理念：“智能采样器”

与其试图阅读庞大图书馆中的每一本书，COREKG 使用了一种称为**核心集理论（Coreset Theory）**的巧妙技巧。你可以将其想象为一个“智能采样器”。

种子（你的兴趣）：首先，你告诉系统你关心什么。在论文中，这些被称为“种子节点”。想象一下你说：“我对鲍勃和科技集团感兴趣。”
过滤器：系统会查看人们曾经向图书馆提出的所有问题。它会过滤掉所有未提及鲍勃或科技集团的内容。现在，它只保留与你的兴趣相关的问题列表。
敏感度分数（重要性计量器）：这是神奇的部分。系统会查看图书馆中的每一个事实（三元组），并问自己：“这个事实对于回答关于鲍勃和科技集团的问题有多重要？”
- 如果一个事实在一百个关于鲍勃的不同问题中被提及，它获得高分。
- 如果一个事实仅被提及一次，它获得低分。
- 如果一个事实与鲍勃或科技集团毫无关系，它获得零分。

采样过程：挑选最佳片段

现在，系统需要构建你的个人摘要。它不仅仅是挑选前 1,000 个事实。相反，它会根据这些分数玩一场概率游戏：

高分事实（对你非常重要）被选中的概率很高。
低分事实被选中的概率很低。
零分事实几乎永远不会被选中。

这被称为基于敏感度的重要性采样。这就像厨师为汤挑选食材：他们会抓一把风味最浓郁的香料（高敏感度），而极少选用那些平淡无味的香料。

秘密武器：加权包

这里是让数学运算生效的棘手部分。如果系统选中了一个“罕见”但重要的事实（即那些不常被选中但至关重要的事实），它会赋予该事实一个高权重。

类比：想象你在进行一项调查。如果你采访了大城市的 100 人，每个人代表 1,000 人。如果你采访了小村庄的 1 人，那一个人就代表 10,000 人。你会给这位村民赋予 10,000 的“权重”，以确保数学计算的公平性。
在 COREKG 中，如果一个事实罕见但至关重要，它会获得高权重。如果一个事实常见且经常被选中，它则获得小权重。

这确保了即使你的摘要非常微小（可能仅占原始图书馆的 1%），在回答你的特定问题时，它在数学上也能表现得与整个图书馆完全一致。

为什么这比旧方法更好？

该论文将其方法与其他“摘要”工具（如 GLIMPSE、PEGASUS 和 APEX2）进行了比较。

旧方法通常试图为所有人总结整个图书馆，或者使用可能遗漏你所需要具体细节的猜测（启发式方法）。
COREKG为每位用户构建一个独特的图书馆。
结果：在针对巨大的现实世界图书馆（Freebase、DBpedia、Wikidata）进行测试时，COREKG 在正确回答问题（更高的准确率）以及保持信息结构完整性方面表现更佳，同时仅使用了极小比例的存储空间。

保证

作者们并非凭空猜测这会奏效；他们通过数学证明了这一点。他们表明，如果你根据这种“敏感度”方法挑选了足够多的事实，你的微型图书馆将给出与大图书馆相同的答案，仅存在微小且可预测的误差范围。

一句话总结

问题：大型知识图谱过于庞大难以使用，而通用的摘要无法满足个人需求。
解决方案：COREKG 为每位用户创建一个微小的、个性化的图谱版本。
方法：它识别你关心的内容，根据每个事实对你问题的有用程度进行评分，并采样最佳事实，同时通过数学加权确保准确性。
优势：你获得了一个快速、小巧且高度准确的摘要，它契合你的特定兴趣，并有数学保证作为后盾。

技术摘要：COREKG——基于核心集引导的知识图谱个性化摘要

1. 问题陈述

知识图谱（KGs）如 Freebase、DBpedia 和 Wikidata 已成为搜索引擎、推荐系统和问答（QA）等应用的核心。然而，其巨大的规模和高度连通性给高效查询、可视化和推理带来了重大挑战。虽然现有的通用知识图谱摘要方法旨在减少数据规模，但它们通常侧重于捕捉全局结构模式，导致生成的摘要过于泛化，无法解决个别用户的具体信息需求。

现有的个性化方法，如 GLIMPSE 和 iSummary，试图根据用户兴趣定制摘要，但面临局限性：GLIMPSE 假设查询历史密集，且缺乏对摘要稀疏性的显式控制；而 iSummary 严重依赖聚合工作负载覆盖率。其他方法如 PEGASUS 和 APEX2 利用启发式规则或热扩散模型，可能缺乏形式化的近似保证，或在处理稀疏和偏斜的查询日志时表现不佳。因此，亟需一种框架，能够在不依赖密集历史数据的情况下，为多样化的用户查询模式提供具有理论保证、计算效率和鲁棒性的个性化知识图谱摘要。

2. 方法论

作者提出了COREKG，这是一个将核心集理论（coreset theory）适配到知识图谱领域的框架。核心集是一个小的加权数据子集，能够以可证明的误差界限近似成本函数。COREKG 通过基于敏感度重要性采样（sensitivity-based importance sampling）对相关三元组进行采样，为每个用户构建个性化的核心集。

2.1 框架概述

COREKG 流水线为每个用户独立运行，包含以下阶段：

预处理与用户建模：
- 种子提取： 每个用户由一组从其查询历史中提取的“种子实体”（直接感兴趣的节点）进行建模。
- 查询过滤： 过滤全局查询日志，仅保留提及至少一个用户种子实体的查询，从而创建用户特定的查询工作负载。
- 归一化： 对 SPARQL 查询进行归一化（去除重复项、扩展前缀），以确保语义一致性。
敏感度分数计算：
- 对于给定的用户 $u$ 及其工作负载 $Q$ ，计算三元组 $t$ 的敏感度 $s(t)$ 。该分数量化了该三元组对用户特定查询的重要性。
- 形式上， $s(t) = \sum_{q \in Q} \frac{1}{|T_q|} \cdot \mathbb{I}[t \in T_q]$ ，其中 $T_q$ 是与查询 $q$ 相关的三元组集合， $\mathbb{I}$ 是指示函数。
- 在用户查询中频繁出现或出现在答案集较小的查询中的三元组会获得更高的敏感度分数。这确保了采样分布是针对个体用户行为而非全局统计数据进行定制的。
核心集构建（采样与加权）：
- 根据概率分布 $p(t) = \frac{s(t)}{S}$ 从原始图 $G$ 中采样三元组，其中 $S$ 是总敏感度。
- 每个采样的三元组 $t$ 被赋予权重 $w(t) = \frac{1}{m \cdot p(t)} = \frac{S}{m \cdot s(t)}$ ，其中 $m$ 是样本大小。这种加权修正了采样偏差，确保核心集上的预期成本与全图上的成本相匹配。
- 结果是一个加权子图（即核心集），它近似了全图针对用户特定工作负载的效用。

2.2 理论保证

本文提供了一个形式化定理（定理 4.1），确立了所构建的核心集 $C$ 以高概率 ( $1-\delta$ ) 在 bounded 相对误差 $\epsilon$ 内近似全图 $G$ 的真实成本。所需的样本大小 $m$ 取决于查询数量 $|Q|$ 和所需的误差界限，但独立于全图的大小 $|T|$ 。

3. 主要贡献

本文概述了四项主要贡献：

COREKG 框架： 一种用于个性化知识图谱摘要的核心集引导方法，将核心集理论适配到图数据，提供可证明的近似保证和实际的可扩展性。
基于敏感度的采样： 一种基于用户特定查询工作负载量化三元组相关性的公式，确保在各种个性化场景下的鲁棒性。
理论界限： 针对用户特定工作负载成本的最坏情况近似保证，该保证独立于全图大小，且所有查询评估直接在核心集上执行。
实证验证： 广泛的实验表明，COREKG 在 Freebase、DBpedia 和 Wikidata 上的查询覆盖率和 F1 分数方面均优于最先进基线（GLIMPSE、PPR、iSummary、PEGASUS、APEX2）。

4. 实验结果

作者在三个真实世界数据集（Freebase、DBpedia、Wikidata）上使用 SPARQL 查询工作负载评估了 COREKG。评估侧重于结构覆盖率（查询模式的保留）和F1 分数（问答准确性）。

性能： COREKG 始终比所有基线获得更高的 F1 分数和覆盖率。例如，在 DBpedia 上，COREKG 实现了**58.64%的 F1 分数和68.07%**的覆盖率，显著优于 APEX2（47.52% F1，42.06% 覆盖率）和 iSummary（19.38% F1，12.55% 覆盖率）。
预算敏感性： 在不同的摘要预算（从 1,000 到 100,000 个三元组）下，COREKG 保持了卓越的性能。虽然其他方法如 PEGASUS 显示出高覆盖率但 F1 分数极低（表明相关性差），但 COREKG 有效地平衡了这两个指标。
消融研究：
- 均匀采样（COREKG-Uniform）： 用均匀随机采样替代敏感度采样导致性能接近零，证实了基于查询的敏感度的必要性。
- 全局工作负载（COREKG-Global）： 移除用户特定条件并使用全局工作负载显著降低了性能，验证了个性化的需求。
- 未加权采样（COREKG-Unweighted）： 对样本分配相等权重导致性能大幅下降，突显了通过加权进行偏差修正的重要性。

5. 意义与主张

本文主张，COREKG 通过将重点从全局或聚合用户建模转向基于理论保证的显式单用户个性化，解决了现有摘要方法中的关键差距。

效率： 通过仅保留基于用户查询模式的相关信息，COREKG 显著降低了存储需求和查询运行时间。
鲁棒性： 与依赖热扩散或密集查询历史的方法不同，COREKG 通过其基于敏感度的采样有效地处理稀疏和偏斜的工作负载。
理论严谨性： 该方法提供了“可证明的近似保证”，确保摘要在保持全图问答语义的同时，误差控制在较小的有界相对误差范围内。

作者得出结论，COREKG 是一种强大的个性化知识图谱摘要方法，为在用户特定相关性和计算效率至关重要的数据驱动应用中处理大规模知识图谱提供了可行的替代方案。该工作明确指出了稀疏工作负载的代表性不足以及缺乏针对单个查询（而非聚合）的保证等局限性，并将这些确定为未来的研究方向。