超图的数学基础（第二章）|数学|新论文|超图

Chapter 2 Mathematical Foundations of Hypergraph

超图的数学基础（第二章）

https://link.springer.com/book/10.1007/978-981-99-0185-2

摘要

在本章中，我们介绍超图的数学基础，并给出用于促进对超图结构深入理解与分析的数学符号。超图由一组顶点和超边组成，它是图的一种推广，其中加权超图用于量化超边或顶点的相对重要性。超图也可分为两大类，即无向超图表示与有向超图表示。后者进一步将一条超边内的顶点划分为源顶点集与目标顶点集，以对更复杂的关联关系进行建模。此外，我们从结构转换与表达能力的角度，讨论了超图与图之间的关系。简单图与超图之间最直观的差异可从阶的大小与邻接的表达方式中观察到。超图可通过团展开、星展开和线展开转换为简单图。此外，基于随机游走与马尔可夫链的证明，建立了具有边独立顶点权重的超图与加权图之间的关系。

2.1 引言

高阶复杂网络建模的重要性已在第1章中讨论过。在本章中，我们介绍超图的基础知识。在超图中，边度通常高于简单图（简单图的边度为2）。不同于图结构仅能利用2度边对成对连接进行建模，超图能够对实际数据之间远比成对关系更为复杂的关联关系进行建模。正因其对数据复杂关联建模的多功能性与实用性，超图上的机器学习已引起越来越多的关注。超图上的机器学习方法因其优势，已被应用于众多现实场景中。在计算机视觉领域，已利用超图完成了广泛的任务，包括图像检索[1]与3D物体分类[2]、视频分割[3]、行人重识别[4]、高光谱图像分析[5]、地标检索[6]以及视觉跟踪[7]。针对这些任务，可将大量对象嵌入到超图结构中。在不同任务中，超图结构可用于刻画各类对象之间的关联关系。在图像检索[3]中，不同图像间的关联可在超图中建模，其中每个顶点表示一幅图像，超边可通过寻找相似的图像特征生成。在3D物体分类[2]中，不同3D物体间的关联可在超图中建模，其中每个顶点表示一个3D物体，超边可基于这些3D物体间的相似性生成。在行人重识别[4]中，可构建一个超图结构，其中每个顶点代表一张个人图像，超边可基于特征空间中的相似性生成。类似的建模尝试也已部署于医学图像分析与生物信息学研究中，用于基因识别[8, 9]、疾病预测[10, 11]、子类型识别[12]以及功能网络分析[13]。在详细展开超图计算范式、超图建模及其他相关方法与应用之前，本章首先介绍超图的预备知识及其多种表示形式。我们还从四个方面将超图结构与图结构进行了对比。

2.2 超图的预备知识

此处简要讨论超图的基本概念。表2.1提供了贯穿本章的超图主要符号与定义。我们首先分别介绍无向超图与有向超图，随后介绍K一致超图、概率超图、超图与二分图的关系，以及超图上的权重。

2.2.1 无向超图

传统的超图结构在顶点之间建立关联，利用单条超边连接多个具有关联的顶点。在关联矩阵 H 中，同一条超边上的所有顶点都被赋值为 1。邻接矩阵 H 按照公式 (2.1) 计算，其元素取值为 0 或 1。每一行代表超图中的每个顶点，列代表所有超边。每一列代表该超边上的顶点集合。

给定如公式 (2.1) 计算的关联矩阵 H H，所有元素取值为 0 或 1。值得注意的是，一条超边上不同顶点的连接权重可能是不同的。例如，某些顶点在超边中连接紧密且权重较高，而其他顶点权重可能较低。也就是说， H H 每一列的和为 1（或者不为 1，视具体应用和目标而定），其数值代表顶点在该超边上的重要性。

存在多种规则可用于确定顶点之间是否存在关联。对于具有图结构的数据，可以通过使用成对边（pairwise edges）和 k-跳（k-hops）来生成超边组；对于没有图结构的数据，可以通过使用特征空间中的邻居来生成。这些方法的详细描述见第 4 章。

2.2.2 有向超图

现实世界与传统无向超图表示并不相符，因为超边可能具有方向性。因此，有向超图结构的表示十分重要。在每条超边中，顶点可进一步划分为两个集合：源顶点集与目标顶点集。在有向超图中，关联矩阵的一个平凡定义[14]如下：

2.2.3 概率超图

在现实世界的关联中，连接的强度不仅可以是二进制数，还可以是从零到一的连续数值。因此，关联矩阵可能是一个元素范围在 0 到 1 之间的连续矩阵，这被用来表示概率超图。

2.2.4 K-一致超图

在许多应用中，超图中的超边可能连接相同数量的顶点，这被称为 k -一致超图。在 k -一致超图中，每条超边恰好包含 k 个顶点，如图 2.4 所示。在此定义下，简单图可以被视为超图的一种特殊情况，即 2-一致超图，其中每条超边仅连接两个顶点。

2.2.6 超图上的权重

需要注意的是，超图上存在不同的权重，这些权重为超图结构的赋值提供了额外信息。这是一种在语义上更优选的超图表示方式，因为超图的不同组件，如顶点、超边甚至子超图，应该对关系建模产生不同的影响。例如，在推荐系统中，用户画像中的权重影响用户属性的分类。如果属性分类不准确，基于该画像的推荐和营销的准确性可能会受到质疑。超图上的主要权重信息类型是超边权重和顶点权重，数值的大小分别指示了超边和顶点的相对重要性。

2.3 图与超图的比较

作为图的推广，图与超图之间的关系是一个基本问题。在本部分中，我们从四个方面详细介绍图与超图之间的关系，即关联的阶数、表示方法、结构转换以及两者上的随机游走（原文为 random work）。

2.3.3 从超图到图的结构转换

与简单图（其中所有边的度数必须为 2）相比，超图利用其无度数限制的超边来编码高阶数据关联（超越成对关系）。从某种意义上说，简单图可以被视为一种特殊情况，即超图上的所有超边度数均为 2。因此，超图和图是可以相互转换的。目前，有许多方法可以将超图转换为简单图。常见的方法有团展开（clique expansion）、星展开（star expansion）和线展开（line expansion），分别如图 2.12、2.13 和 2.14 所示。

与图学习相比，在超图学习中，数据在更高层次上相关，关联模型也被扩展到了更高层级，从而在实践中带来了性能的提升。这只是图和超图本质中显而易见的一部分。接下来，我们在随机游走 [20] 和马尔可夫链 [21] 的辅助下，从数学推导的角度深入探讨图与超图之间的关系。随后，我们对超图和图进行了数学上的比较。证明结论表明，从随机游走的角度来看，具有边独立顶点权重的超图等价于一个加权图，而具有边依赖顶点权重的超图则无法简化为加权图。

2.4 总结

在本章中，我们介绍了超图基础的数学定义及其解释。随后，我们也展示了有向超图的表示，它不同于无向超图，代表了超边内部顶点之间的关系。最后，我们从转换和表达能力的角度讨论了图与超图之间的关系。图与超图之间最直观的差异体现在低阶与高阶表示以及邻接矩阵与关联矩阵上。团展开、星展开和线展开是将超图转换为简单图的方法。我们还从随机游走的角度展示了图与超图之间的关系。具有边独立顶点权重的超图等价于一个加权图，而在图/超图的信息传播过程中，具有边依赖顶点权重的超图无法简化为加权图。