超图协同最优传输：度量与范畴性质

超图协同最优传输：度量与范畴性质

Hypergraph Co-Optimal Transport: Metric and Categorical Properties

https://arxiv.org/abs/2112.03904

摘要

超图捕获了数据中的多路关系，因此它们在高阶网络分析、计算机视觉、几何处理和机器学习中已得到诸多应用。在本文中，我们利用最优传输的相关要素，为研究超图空间构建了理论基础。通过在超图的节点和超边上赋予概率测度，并结合能够捕获局部与全局结构的关系信息来丰富超图，我们获得了一个用于研究全体超图集合的通用且鲁棒的框架。首先，我们基于Redko等人的协同最优传输框架引入了一种超图距离，并研究了其理论性质。其次，我们将把超图转换为图的常见方法形式化为超图空间与图空间之间的映射，并研究了这些映射的函子性质与Lipschitz界。最后，我们通过多个实例展示了我们的超图协同最优传输（HyperCOT）框架的多功能性。

关键词：超图，超图度量，最优传输，范畴论，超图匹配

1 引言

对超图的研究源于高阶网络分析。图通常用于编码网络安全、生物学、社会学和物理基础设施等复杂系统中的数据，其中节点代表实体，边代表实体之间的成对关系。然而，现实世界的数据包含丰富的多路关系。例如，Patania 等人 [50] 研究了来自 arXiv 的科学论文合著关系，其中一篇论文代表了几位作者之间的多路关系；Cencetti 等人 [16] 发现，在以异质动力学为特征的人类面对面交流中，高阶交互无处不在。

这些多路关系能更好地被超图捕获。一个超图由一个节点集合和一个节点子集集合组成，其元素被称为超边。超图推广了图的概念，图仅仅是每个超边恰好包含两个节点的超图。例如，超图可用于表示分子结构，其中节点是单个原子，超边代表原子对之间的共价键或多个原子之间的多中心键（见 [8, 第7.1章] 和 [39]）。超图还可以对细胞网络进行建模 [37]，其中蛋白质复合物是由多个蛋白质组成的超边。Lotito 等人证明了高阶模体在社会学、生物学和技术领域的多个超图数据集 [45] 中所具有的信息价值。

超图也出现在计算机视觉、几何处理、模式识别和机器学习的应用中，在这些领域中，在两个特征集之间建立对应关系是一个基本问题。对应问题传统上被表述为图匹配问题 [32, 70]：每个图的构建均以节点表示特征，以边表示特征之间的成对关系。例如，在几何处理中，特征的绝对位置不如其成对关系重要，例如在施加平移和旋转不变性时。然而，在建立对应关系时，成对关系不足以纳入特征之间的高阶关系——这可以通过超图匹配问题来解决 [17, 42]。

近年来，Gromov-Wasserstein (GW) 框架——最初是作为比较度量测度空间的工具而开发的 [46, 47]——已被扩展到概率图匹配任务中 [19, 22, 34, 63, 71, 75, 76]。该框架的详细内容见第2.1节，但其大致思路如下。最优传输度量通常用于比较公共度量空间上的概率分布，并被广泛认为是量化几何测量中不确定性的强大框架 [52, 62]。相比之下，GW 距离用于获取不同空间之间的对应关系，从而允许对先验不可比的空间进行比较 [46, 47]。GW 距离基于寻找两个度量空间中点之间的概率对齐，以最小化整体度量失真目标。该方法的诸多优势包括可通过梯度下降 [28, 53] 或反向传播 [74] 进行计算，在图划分 [21, 75] 等任务中达到最先进的性能，以及具有底层的黎曼理论框架 [20, 65]。这些成功推动了面向超图的 GW 框架的开发，这也是本文的目标。我们的贡献包括：

• 我们扩展了 Redko 等人 [55] 的协同最优传输（co-optimal transport）框架，以定义一种基于最优传输的超图间距离。为了奠定坚实的理论基础，我们引入了一种广义的超图概念，称为测度超网络（measure hypernetwork），见第 2.2 节。随后，我们建立了超图距离的基本性质；特别是，我们证明了它是测度超网络空间上的伪度量（pseudometric），该伪度量在模去距离为 0 的等价关系后，诱导了测度网络空间上的完备测地度量（Theorem 1）。
• 我们在测度（超）网络空间上引入了范畴结构。通过这一视角，我们将把超图转换为图的常见变换（例如，关联图、团扩展和线图）作为从超网络范畴到网络范畴的函子进行研究。我们还研究了它们关于我们的超网络距离以及网络空间上的 GW 距离的 Lipschitz 性质。我们证明了关联图映射是将我们的距离映射到 GW 距离的一种新变体的函子等距映射（Theorem 10）。接着，我们引入了团扩展和线图映射的单参数族，并证明了它们是 Lipschitz 函子（Theorem 11）。
• 我们获得了一些关于测度（超）网络范畴的结构结果。命题 17 展示了文献中某些度量的同构概念与范畴论意义上的同构是等价的。我们范畴中各种极限构造的（不）存在性在命题 21 和 22 中得以确立。
• 我们在第 5 节通过多个示例展示了我们要用于超图匹配和比较的开源计算框架 [1]。我们的方法被整合到一个基于超图简化拓扑算法 [78] 的框架中；特别是，我们的超图距离被用于突显现实世界数据集中感兴趣的简化层级。 1.1 相关工作

超图度量、相似度与不相似度测量。 尽管有大量数据可以建模为超图，但文献中对超图之间的度量尚未进行广泛探索。Karonski 和 Palka [36] 将定义在同一节点集上的超图视为聚类，并定义了这些聚类之间的 Marczewski–Steinhaus (MS) 距离。MS 距离是在集合的 Hausdorff 度量的一种推广基础上修改得到的。Karonski 和 Palka 还讨论了由具有相同终端顶点集的有向树（arborescences）生成的超图之间的距离。与 MS 距离相比，我们的超图距离不要求超图定义在同一组节点上；更重要的是，我们的距离具有良好的度量性质，显式编码了节点与超边之间的结构关系，并自然衍生出有意义的超图匹配。Lee 等人 [42] 将编辑距离从图推广到了超图。然而，这种距离并不实用，因为图编辑距离的计算是 NP 难的 [77]，且近似是 APX 难的 [44]。Smaniotto 和 Pelillo [61] 最近利用最大公共子超图定义了属性超图之间的距离；然而，计算两个超图之间的最大相似性子超图同构是 NP 完全的。相比之下，通过遵循协同最优传输的优化程序，我们的超图距离可以被高效地近似。另一种超图比较方法见于 [67]，该方法将超图转换为图，并应用标准的图相似度或不相似度度量。超图也可以被编码为张量 [3]，从而可以通过它们的张量表示进行谱比较。[27] 中的工作描述了一个原则性的超图匹配框架，并提议使用该框架超越等距不变形状匹配，以获得在相似、仿射和射影变换下的不变性。然而，[27] 中的框架为每个超边构建固定大小的超图，不适用于输入数据为任意超图的情况。相比之下，我们的超图距离可以接受任意一对超图作为输入。

最优传输与 Gromov-Wasserstein 距离。 如上所述，Gromov-Wasserstein (GW) 距离本质上只需要对要比较的空间中编码成对关系信息的方阵 [19]，因此非常适合通过邻接矩阵、最短路径距离或谱表示来比较图 [21, 71, 76]。然而，超图通常编码的不仅仅是成对关系；我们将 GW 框架扩展到超图的策略是直接处理多路关系（在有限设置中建模为编码节点-超边关系的矩形矩阵），并利用 [55] 中最近开发的协同最优传输框架。使用该框架，我们能够在比较超图时同时推断节点-节点和超边-超边的对应关系。

2 超网络：理论形式化

本节介绍了测度超网络（measured hypernetworks）的基本概念及其之间的距离。

2.1 背景：测度网络

图（graph）是一个二元组 (V,E)，其中 V 是节点（nodes）的集合，E 是 V的 2 元子集的集合，其中每一个子集被称为一条边（edge）。下文给出了图这一概念的深远推广。

2.2 测度超网络与超网络距离

超图是一个二元组 (X,Y)，其中 X 是节点的集合，Y 是 X 的子集族，其中的每个子集被称为一条超边。图 1 展示了一些简单的超图以及不同的超图可视化技术。

我们现在准备好定义测度超网络之间的距离，这是 Redko 等人在 [55] 中引入的协同最优传输框架的直接扩展。

2.3 超网络距离的性质

在下述示例中，我们指出，基本弱同构的概念为描述超图简化中使用的一种过程（称为节点与超边坍缩 [78]）提供了一种形式化框架。

3 图化

超图分析与机器学习中的一个常用技术是将超图转换为传统图，后者具有更易处理的结构（例如，[1, 54, 67, 73]）。在本节中，我们将图化形式化为从测度超网络范畴到测度网络范畴的函子研究。

3.1 超图到图的变换

原文链接：https://arxiv.org/pdf/2112.03904