论文浅尝 - KDD2020 | 真实世界超图的结构模式和生成模型
论文笔记整理：毕祯，浙江大学硕士，研究方向：知识图谱、自然语言处理。
链接：https://arxiv.org/abs/2006.07060
动机
图已被用作对人或物体之间的成对关系建模的强大工具。而超图是更广泛概念的一种特殊类型，其中每个超边可以由任意数量的节点组成，而不是仅由两个组成。大量的现实世界数据集都是这种形式的。比如电子邮件的收件人列表，参与讨论主题的用户或在线问题中标记的主题标签等。由于这些情况表示形式复杂且缺少适当的工具，因此在研究中很少会去关注探索这些问题的建模与算法。
本篇论文根据经验研究了多个跨领域的真实世界超图数据集。为了进行深入研究，引入了多级分解方法，该方法通过一组成对图表示每个超图。每个成对图（称为k级分解图）捕获了k个节点的子集对之间的交互。通过经验的总结，在每个分解级别，所研究的超图都遵循五个结构特性或者指标。这些属性用作评估超图的逼真度的标准，并为超图生成问题奠定基础。文章最后提出了一种超图生成器，采取了非常简单的思路，但是能够满足这些评估指标。与此相比的是其他对比模型则很难达到同样的效果。
背景
图1 超图的例子
超图是图的一般化，其中边可以连接任意数量的顶点。相反在普通图中，一条边正好连接两个顶点。在图1中，假设顶点代表文章，每条边代表两个顶点享有同一个作者。如果使用简单的图结构来表示，就会丢失“同一作者发表多篇文章”这样集合的信息。实际生活中存在着大量类似的图结构，而超图是相对合适的表示方法。
多级分解方法
定义：
其中：
图2 超图的多级分解
利用分解图具有几个优点：
（1）子集交互：分解后的图揭示了节点子集之间的子集交互。
（2）成对图表示：分解后的图可以使用成对图的现有度量进行分析。
（3）没有信息丢失：原始的超图可以从分解后的图中恢复。
观测指标
论文证明了下列的结构模式在真实超图的分解图的每个级别中均有效。
（P1）Giant connected component：巨型连接分量
此属性意味着存在一个包含大量节点的连接分量，并且该比例显着大于第二大连接分量（至少大70倍）。网络中的大多数节点都相互连接。此属性用作其他属性的基础。
（P2）Heavy-tailed degree distribution：重尾度分布
节点的度数定义为其邻居数。此属性意味着度分布是重尾的，即以比指数分布慢的速率衰减。这可以用“rich gets richer”来部分解释：高级节点更有可能形成新的链接。
（P3）Small effective diameter：有效直径小
分解的图通常不完全连接，论文采用的定义，其中有效直径是最小距离d，使得所有连接对中的大约90％可以通过最长d的路径到达。此属性意味着实际数据集中的有效直径相对较小，并且大多数连接对可以以较小的距离到达。需要注意的是，空模型也具有此特征，并且在这方面比较实际数据集和相应的空模型不会产生一致的结果。
（P4）High clustering coefficient：高聚类系数
利用聚类系数C，定义为所有节点的局部聚类系数的平均值。每个节点v的局部聚类系数Cv定义为：
此属性意味着实际数据集中的统计量明显大于相应的空模型中的统计量。由于邻居结构产生大量三角形，因此此属性表示网络中存在许多邻居结构。
（P5）Skewed singular values：偏斜奇异值
此属性意味着奇异值分布通常是重尾分布，并且以与模式P2相同的方式进行验证。
HpyerPA生成器
生成器HyperPA反复向超图引入新节点，并形成新的超边缘。添加节点后，HyperPA会创建k个新的超边缘，其中从预定分布NP中采样了k个。对于此新节点引入的每个新超边缘，其大小s是从预定分布S中采样的。当选择其他节点填充此新超边缘时，它将考虑包含s-1个节点的所有组。在所有此类群体中，每个群体被选中的机会与其程度成正比。每个组的程度定义为包含该组的超边缘的数量。
评测方法
（P1）如果在该级别的分解图生成的超图保留一个巨大的连通分量，给出1分。
（P2）生成的度分布与实际分布之间的相似性由Kolmogorov-Smirnov D统计量度，其中F，F'是累积度分布 相应的实图和生成的分解图。对D统计量小于0.2的生成器给予1分。
（P3）我们希望生成的有效直径d'接近实际值d。由于P3为“有效直径较小”，因此d'不应太大。论文采用验收范围为（2d/3，4d/3）的启发式方法。如果d在接受范围内，则给出1分。
（P4）论文将接受范围试探为(2c/3, min(4c/3, 1))，如果c′在接受范围内，则给出1分。
（P5）与P2相似，真实数据集和生成的数据集的奇异值分布之间的相似性由Kolmogorov-Smirnov D统计量度。对D统计量小于0.2的生成器给予1分。
实验结果及结论
生成器的结果在表中进行了数字比较。HyperPA，NaivePA和子集采样这两个表的总分分别为64、49和57。其中论文提出的模型HyperPA得分最高。如果不考虑子集交互，变量S、NP和n不足以重现pattern，因为即使使用S、NP和n，NaivePA和子集采样也无法做到。
论文工作的贡献是三方面的：
多级分解：首先提出多级分解作为研究超图的有效手段。多级分解有几个好处：（1）它捕获超图内的组交互；（2）其图形表示为利用现有工具提供了便利；（3）它代表了原始超图而没有信息丢失。
实际超图中的模式（pattern）：论文介绍在13个现实世界超图中持有的一组常见模式。具体来说在不同的分解级别是巨型连通分量、重尾度分布、小有效直径、高聚类系数和偏斜奇异点的价值分布。
有效仿真的超图生成器：最后引入HyperPA，这是一种超图生成器，它很简单，但是能够在不同分解级别上再现真实世界超图的模式。通过保持超图中节点的子集交互的连通性，HyperPA在重现模式方面表现出比其他基准模型更好的性能。
OpenKG
开放知识图谱（简称 OpenKG）旨在促进中文知识图谱数据的开放与互联，促进知识图谱和语义技术的普及和广泛应用。
点击阅读原文，进入 OpenKG 博客。