超图不变量与变换的稳定性

超图不变量与变换的稳定性

Stability of Hypergraph Invariants and Transformations

https://arxiv.org/pdf/2412.02020

摘要：

图是复杂系统中对成对交互进行建模的基本工具。然而，许多现实世界系统涉及多方交互，这些交互无法被标准图完全捕获。超图通过允许边连接任意数量的顶点来推广图，提供了一个更具表达力的框架。在本文中，我们受度量空间的Gromov-Hausdorff距离启发，在超图空间上引入了一种新的度量。我们建立了常见超图变换的Lipschitz性质，这些变换将超图映射为图，其中包括一种与单链接层次聚类有关联的新型图化方法。此外，我们通过来自基本汇总统计量和拓扑数据分析技术的不变量，推导出了超图距离的下界。最后，我们在最优传输的背景下探讨了代价函数的稳定性性质。我们在这一方向上的结果考虑了Hausdorff映射的Lipschitz性，以及代价函数极限下非负交叉曲率性质的保持性。

1 引言

图是表示包含交互作用的数据的标准形式，在生态学[16]、基因调控[30]、蛋白质柔性[19]、社交网络分析[10]以及众多其他领域的应用中无处不在。由于其固有结构，图仅能捕获对象之间的成对交互，而在对复杂系统进行建模时，考虑多方交互往往是自然的。超图是一种类图结构，它更一般地允许任意数量的顶点通过一条边相互关联。超图能够展现捕获诸如生态系统营养级之间或合作网络中论文之间复杂交互作用所需的多种连接可能性，而这些在更基础的图表示中将会丢失[15]。图1展示了一个源自基因关系数据集的超图示例。

本文从度量几何的视角探讨图与超图理论中的若干问题。鉴于其在纯数学与应用数学中的普遍性，亟需能够比较图结构（尤其是定义于不同节点集上的图结构）的方法；近几十年来得到充分发展的一个途径是通过类Gromov-Hausdorff构造对它们进行比较。Gromov-Hausdorff距离著名地为紧度量空间赋予了度量结构[18]，且近年来已被扩展用于比较（广义）图结构[6, 8]。具体细节见下文第2.1节，但此类图距离的基本机制在于：在待比较图的节点之间寻找一种对齐方式，使得某一畸变函数最小化。

本文中，我们将图之间的Gromov-Hausdorff距离推广为超图空间上的一种新度量。由于超图的边编码了节点间非严格成对的关系，超图间的比较需同时建立节点与边的对齐；Gromov-Hausdorff距离的结构为此类推广提供了自然形式，具体见定义2.13。尽管该新度量在现实超图数据分析中具有潜在应用，但本文的重点在于该度量的理论性质。具体而言，本文的贡献集中于该度量的稳定性性质——即证明某些超图不变量定义了至相对简单表示空间的Lipschitz映射。

1.1 主要结果与大纲

我们现在概述本文并描述我们的主要贡献：

1.2 相关工作

除了上述指出的相关工作和结果引用外，我们要将本文的方法与文献 [9] 中的作者（及其合作者）的方法进行比较。那篇论文也考虑了类超图对象通用模型上的度量；其中的主要区别在于，超图的节点和边被赋予了概率测度，从而使得最优传输理论中的方法变得适用。具体而言，那里的构造借用了 Mémoli 的 Gromov-Wasserstein 距离 [25, 7] 以及最近引入的 co-optimal transport（协同最优传输）框架 [29] 的思想。图化（graphifications）的 Lipschitz 性质在 [9] 中也被考虑过，但这里使用的证明技术是新颖的（而且我们相信，事实上，它们可以被调整以提供比 [9] 中出现的更好的 Lipschitz 常数）。此外，本文使用的是 Gromov-Hausdorff 距离的一种变体（而不是 Gromov-Wasserstein 距离），这可以说是一个在理论上更基础的构造。

我们在引言的最后对阐述风格做一点说明。由于我们的一些结果是将 [26, 6, 28, 8, 22] 的结果扩展到超网络的设定，我们通常旨在对我们的贡献进行精简的陈述。我们关于超网络的所有结果都是新颖的，但是当它们的证明可以通过对度量空间或网络背景下现有证明进行微小调整而得出时，我们会省略或简述证明，并指引读者阅读文献中的相关结果——例如命题 2.17、定理 4 和定理 5 就是这种情况。另一方面，我们的几个结果是完全新的，或者需要与之前出现过的不同的证明技术，在这种情况下我们会提供完整的细节——参见，例如，定理 3 和定理 7。

2 超网络与超网络距离

本节介绍了全文将要研究的主要结构。首先，我们在定义中将（加权）超网络定义为类度量空间结构，这为超图的概念提供了一种自然且深远的推广。其次，我们扩展了 Gromov-Hausdorff 距离的构造，以定义超网络结构之间的一种新距离。我们首先回顾一些相关背景。

2.1 网络 Gromov-Hausdorff 距离

Gromov-Hausdorff (GH) 距离最早由 Edwards [14] 研究，后来被 Gromov [18] 重新发现并普及，它是度量几何中的一个基本工具。我们参考 [2] 作为其基本性质的标准参考资料，并参考 [26]，其中建立了进一步的重要性质，例如基于度量不变量的某些下界。

2.2 加权超网络

超图的概念是对图的概念的推广：超图中的边允许连接任意数量的顶点，而非仅两个。我们如下对此进行精确化。

超图通常被可视化为维恩图，其中节点集绘制为点的集合，超边则描绘为阴影区域——参见图2的示例及其二值关联函数。图5展示了一个加权超图及其对应的加权关联函数。通过放弃 Y⊂P(X) 的要求，可获得一种灵活的超图模型。仿照文献[6]在图的一般模型设定中以及文献[9]在带有附加概率数据的超图模型（即所谓的测度超网络）设定中使用的术语，我们如下定义我们的研究对象。

2.3 超网络之间的距离

我们现在定义超网络之间的一种距离，该距离在结构上类似于定义2.1中的网络Gromov-Hausdorff距离

。

2.4 超网络距离的映射表述

下一个结果表明，超网络 GH 距离的映射表述等于定义 2.13 中定义的超网络 GH 距离。这模仿了文献 [6, 命题 9] 中证明的网络 GH 距离的情形。此处的证明是相似的，因此我们省略它。我们的重构形式将在下文第 4.2 节中用于将超网络 GH 距离与持久同调联系起来。

3 图化

超图分析中的一种常用技术是将超图转换为具有更易处理结构的传统图 [31]。在本节中，我们考虑几种特定的图化（graphifications），或者说将（加权）超图转换为（加权）图的操作。本节的目标是证明这些操作关于

是 Lipschitz 的。

3.1 图化映射的定义

直观上，二部图化通过定义两个节点集来表示超图——一个对应于原始超图的节点，另一个对应于超边——并以一种反映原始超图结构的二部方式将它们连接起来。

应当注意到，二部图化是可逆的，即原始超图可以从其二部表示中重构出来。这一点将在下文的第 3.2 节中得到验证。后续的操作不具有相同的性质。

这些图化操作的简单示例在图 3 中展示。团扩展和线图映射在网络函数层面的行为在图 4 中明确展示。

3.2 二部网络

3.3 亲和网络

定义3.3中引入的团扩展和线图图化仅考察节点与超边之间的局部结构：假设 ωω 编码了一个加权关联矩阵，团扩展仅在存在某个同时包含两个节点的超边时才连接它们，类似的情形也适用于线图。我们在下文提出一种称为亲和网络的新构造，它以一种能更全局地理解节点（或超边）如何相互关联的方式，扩展了上述图化方法。我们首先从一些预备概念开始。

我们将滥用记号，并在此后省略能量与亲和度的下标。泛函的定义域由上下文即可明确，这将使后续方程更为简洁。我们现在准备定义一对新的图化映射。

注记 3.9. 推论 3.8 与文献 [9, 定理 11] 密切相关，该文献为在节点和超边集上引入权重（以概率测度的形式）的团扩展和线图映射的版本建立了类似的 Lipschitz 界。那篇文章并未考虑广义亲和网络构造，且其证明策略与定理 3 和推论 3.8 的证明策略不同。我们在此给出的证明提供了改进的 Lipschitz 界，并且我们推测它们可以被调整以加强加权情形下的结果。

然而，节点1和5之间的亲和度为0.4，这是它们之间所有链上的最大能量，这样一条链可以通过超边B构建。如果我们要计算完整的节点亲和网络，其加权邻接矩阵可见图6（左）。我们在图6（右）中通过类似树状图（dendrogram）的图（参见[3]）进一步表示了该超网络的亲和结构。网络的节点出现在其对角线元素所在的层级（因为这是其最大值），然后当节点子集的每个元素都大于或等于该值时，节点在该层级被聚类。

4 下限

本节基于经典Gromov-Hausdorff距离背景下出现的类似下界[26, 8]，介绍了超网络Gromov-Hausdorff距离的几个可计算下界。

4.1 基本不变量

超网络GH距离的第一组下界涉及有限超网络的几个不变量。

由此得到的网络不变量对应于文献[26, 第3节]（在度量空间背景下）和[8, 第4节]（在网络背景下）中曾考虑过的那些不变量。

本节的主要定理表明，这些不变量关于超网络Gromov-Hausdorff距离是稳定的。为了精确地陈述该定理，我们回顾一下度量空间 (Z,d) 中一对子集 A 和 B 之间的Hausdorff距离由下式给出：

我们得到以下直接推论。

推论 4.2. 定义 4.1 中的每个超网络不变量在弱同构下都是不变的，即定理 4 中引入的比较这些不变量的方法在超网络弱同构时结果为零。

例 4.3. 考虑图 7 中所示加权函数的两个超网络。这些超网络的各种不变量测量值记录在表 1 中。方程 (21) 和 (20) 给出了 0.05 的下界。此外，在考虑节点不变量时，方程 (17)、(18) 和 (19) 也给出了相同的 0.05 下界。然而，如果我们考虑后三个不变量的边变体，则三者均得到 0.15 的下界。

4.2 持久同调

持久同调是拓扑数据分析（TDA）的一种方法，特别适用于理解数据集的底层拓扑结构，并在计算生物学、图像分类、网络分析等诸多领域有大量应用；关于这些应用的进一步参考文献，请参见综述文章 [13, 17, 1]。在本小节中，我们假设读者熟悉 TDA 和持久同调的基本构造，如专著 [11] 中所述。

最常见的情形是，持久同调方法应用于具有单纯映射的单参数单纯复形族——这种结构被称为过滤单纯复形（filtered simplicial complex）。我们现在描述一个自然关联于任意有限超图的过滤单纯复形。下文所见的 Dowker 过滤是文献 [6] 中网络 Dowker 过滤的推广，其起源可追溯至 [12]。

5 代价函数的稳定性

前两节考虑了超网络Gromov-Hausdorff距离的下界，其灵感来源于将超网络视为超图广义模型的视角。在本节中，我们转变这一视角，将超网络视为代价函数，例如最优传输理论中出现的那些（参见例2.8）。由于这一转变，我们放弃了最后两节中的有限性假设，转而研究一般的超网络。

5.2 非负交叉曲率

在近期的工作 [22] 中，作者引入了最优传输理论 [24] 中著名的 Ma-Trudinger-Wang 条件的一个综合版本（synthetic version）。与其中使用的形式体系相比，可以立即看出它很好地契合了本文提出的框架。我们回顾 [22, 定义 1.1]，并使用本文的术语进行陈述。

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