高阶网络表征：图框架综述（第二版）

高阶网络表征：图框架综述（第二版）

Representing Higher-Order Networks: A Survey of Graph-Based Frameworks(Second Edition)

https://philarchive.org/archive/FUJRHN

摘要

许多现实世界的现象可以自然地用图和网络进行建模。然而，经典图模型通常局限于成对交互（pairwise interactions），可能无法充分捕捉实践中出现的更丰富结构。高阶图形式化方法（higher-order graph formalisms）通过纳入多路（multiway）、层级（hierarchical）、时序（temporal）、多层（multilayer）、递归（recursive）以及基于张量（tensor-based）的交互，扩展了这一框架，从而为复杂系统提供更具表达力的表征。

本书全面概述了可用于建模高阶网络的数学概念。书中综述了基础概念、外延性框架（extensional frameworks）以及新近引入的形式化方法，着重阐述其结构原理、相互关系及建模作用。本书旨在提供一个统一的视角，帮助读者比较多样的高阶网络模型，并为理论研究与实际应用识别合适的工具。

本书为第二版（Edition 2.0）。主要新增内容包括若干概念的补充，以及对排版错误和解释说明的修正与完善。

关键词：超图（Hypergraph），超超图（Superhypergraph），高阶图（Higher-Order Graphs）

1 引言

1.1 高阶图

众所周知，许多现实世界的现象可以使用图和网络进行建模 [1, 2]。然而，许多此类系统展现出超越成对交互（pairwise interactions）的结构：它们可能涉及多路关系（multiway relations）、层级组织、嵌套或递归依赖、时间演化，或多层耦合。经典图模型通常不足以以数学上忠实的方式表示这些特征。

为了解决这一局限性，人们已经开发了广泛的高阶形式化方法（higher-order formalisms），包括超图（hypergraphs）[3]、超超图（superhypergraphs）[4]、基于元图的模型（metagraph-based models）[5]、基于单纯形和胞腔复形的框架（simplicial and cell-complex-based frameworks）、多层和时间网络，以及更近期的范畴论或语义方法。例如，超超图通过允许顶点域本身是分层的，从而扩展了高阶网络模型，使得集合值（set-valued）和迭代结构能够直接在对象域中进行编码 [4]。结果是，高阶图论已经发展成为一个广泛且异质的领域，许多概念源自不同的数学视角和建模目标（参见 [6, 7, 8, 9, 10, 11]）。

高阶网络（或高阶结构）的概念已应用于如下领域。当然，应用范围并不局限于这些：

• 交通与物流网络（参见 [12, 13, 14, 15, 16]）：与普通成对图相比，高阶图能更自然地表示多站配送计划、枢纽协调、共享路线以及群组流约束。
• 社交网络分析（参见 [17, 18, 19, 20, 21, 22]）：它们对群组对话、团队互动、重叠社区和层级成员关系进行建模，超越了简单的人与人之间的链接。
• 知识表示与语义网络（参见 [23, 24]）：它们对于在知识系统中编码多实体关系、类型化事实、上下文关联和层级语义结构很有用。
• 分子与化学结构分析（参见 [25, 26, 27]）：它们可以描述化学系统中的多原子相互作用、反应机制、分子复合物以及高阶结构依赖。
• 神经科学与脑网络（参见 [28, 29]）：它们支持对集体神经相互作用、多区域同步、分层脑连接以及时间依赖的功能组织进行建模。
• 机器学习与图神经网络（参见 [30, 31, 32, 10, 33]）：高阶图应用于涉及群组、层级或嵌套结构的关系的学习任务中，例如超图神经网络（HyperGraph Neural Networks）及相关模型。
• 推荐系统（参见 [34, 35, 36]）：它们可以同时捕捉用户、物品、上下文、时间和属性交互，提供比普通二部图更丰富的关系表示。
• 供应链与组织系统（参见 [37]）：它们对供应商、资源、部门和流程之间的多方依赖进行建模，包括层级和跨层级的协调结构。
• 通信与信息网络（参见 [38]）：它们适合表示多播通信、分层协议、群组传输以及动态变化的高阶连接模式。
• 决策制定与运筹学（参见 [39, 40, 41, 42]）：它们可以在复杂决策问题中表达交互准则、分组备选方案、层级评估结构以及感知不确定性的关系依赖。

1.2 我们的贡献

已经开发了多种多样的用于表示高阶网络的数学框架。然而，这些框架通常分散在不同的数学传统、术语和应用领域中，这使得系统性的比较变得困难。出于这个原因，我们认为编写一本将这些概念汇集在一个连贯参考中的综述类书籍是有价值的。

因此，本书提供了可用于建模高阶网络的数学概念的广泛且结构化的概述。其目的是为这些形式化方法提供一个统一的切入点，阐明它们的基础思想，并强调它们的共同特征及其本质差异。通过这种方式，本书旨在支持进一步的理论发展以及在人工智能（AI）和相关领域的应用。

然而，值得注意的是，这里收集的概念并非在单一统一的意义上是“高阶”的。一些框架通过增加交互的元数（arity）来推广图，如在超图类模型中。另一些引入了层级、嵌套或递归，如在超超图类构造中。还有一些通过层、时间索引或多方面组织来编码高阶性，如在多层和时间网络中。最后，一些方法完全源自不同的数学语义，包括运算子（operadic）、幺半（monoidal）、关系、基于张量、基于闭包和余代数的观点。

为了使这种多样性更易于理解和比较，本书中的概念根据摘要表中采用的实际分类被组织成四个 broad families（大类）：

1. 组合、集合论和序论结构，
2. 几何、拓扑和基于复形的结构，
3. 因式分解、约束、分层、时间和基于张量的结构，以及
4. 语义、组合、基于知识和逻辑的结构。

作为参考，本书中使用的高阶网络概念的实用四大家族组织形式见表 1.1。

2 组合、集合论与序论族

在本章中，我们描述高阶图的主要类型。作为参考，本书中探讨的组合、集合论和序论高阶结构列于表 2.1 中。

2.1 超图与超超图

超超图通过允许顶点域本身是分层的，从而扩展了高阶网络模型。具体而言，从一个基础集开始并迭代幂集运算；顶点（通常称为超顶点）可以是位于该迭代规定层级上的集合值对象，而（超）边则编码这些高层顶点之间的关联 [4]。相关的层级构造已在应用中得到探索 [43]。

此外，已知有几种超图的扩展，包括模糊超图 [44, 45, 46]、中性超图 [47, 48, 49] 和 plithogenic 超图 [50]。同样，超超图的扩展，如模糊超超图 [41]、中性超超图 [51, 52] 和 plithogenic 超超图 [53, 54, 55] 也已被研究。此外，作为有向图概念，以下概念是已知的：有向超图 [56, 57]、双向超图 [58]、有向超超图 [59, 60] 和双向超超图 [61, 58]。如需更广泛的概述，我们建议读者参考综述专著 [62]。

2.2 多重图与迭代多重图

多重图是一种允许平行边和自环的图；形式上，边是顶点之间可能具有重数的多重集 [68, 69, 70]。作为扩展，已知的概念包括模糊多重图 [71, 72, 73]、二分多重图 [74, 75]、完全多重图 [76, 77]、中性多重图 [68, 78]、软多重图 [79] 和有向多重图 [80]。迭代多重图使用迭代多重集作为顶点对象，因此顶点本身可以是递归嵌套至深度 n 的多重集。

2.3 h-模型

一个 h-模型是一个结构 ⟨S, H, I⟩，由一个基集 S、S 上超图的一个有限集合 H，以及一个解释映射 I 组成，该映射将每个命题原子指派为 H 中的一个超图 [82]。

一个 sh-模型可被视为基于超超图的 h-模型对应物：它不是为每个命题原子指派一个超图，而是指派一个固定基集上的有限 n-超超图。

2.4 无链子集

偏序集（poset）的一个 k-无链子集是一个不包含长度为 k 的严格递增链的子集；等价地，它避免 k 个相互可比的元素 [83]。

2.5 幂集图

幂集图的顶点由一个集合的非空真子集给出，边存在于通过包含关系可比的子集之间 [84]。迭代幂集图重复应用非平凡幂集构造；在每一深度，顶点是嵌套子集，当通过包含关系可比时相邻。

2.6 约翰逊图

约翰逊图的顶点由 [n] 的 w-子集给出，边连接相差一个元素的顶点对 [85, 86, 87]。约翰逊图的相关概念也是已知的，例如广义约翰逊图 [88, 89]。

2.7 克涅瑟图

克涅瑟图（Kneser graph）的顶点由 [n] 的 k-子集给出，边连接不相交的顶点对 [91, 92, 93, 94]。相关概念也是已知的，例如克涅瑟超图 [95, 96]、二分克涅瑟图 [97, 98]、稳定克涅瑟图 [99, 100] 和广义克涅瑟图 [101, 102]。

2.8 元图与迭代元图

元图以图作为顶点；边表示这些图之间带标签的关系，满足关系定义的关联约束（参见 [103, 104, 105, 106, 107]）。元图也被称为图之图。迭代元图重复这一构造：顶点是较低深度的元图，并通过提升的关系递归地链接它们 [103]。

定义 2.8.1（元图（Metagraph；图之图））。[103] 固定一个有限图的非空全集 G（默认无向且无环），并固定 G 上二元关系的一个非空族 R，即

2.9 元超图与元超超图

元超图是一种顶点为对象的超图；每个超边通过带标签的关系关联有限的顶点集（参见 [5, 108]）。它也可以被描述为超图的超图。

元超超图的顶点为超超图；超边关联它们的有限集合，且受关系标签约束 [5]。它也可以被描述为超超图的超超图。

成立，因此按照定义 2.9.1 的意义，M 是 (U, R) 上的元超图。直观上，M 是一个“超图之超图”，其元超边断言某些城市级超图族在产品目录上存在强烈的重叠。该示例的概览图见图 2.9。

2.10 嵌套超图与嵌套超超图

嵌套超图允许超边将其他超边作为元素包含在内，并通过秩强制实施无环的良基嵌套 [109]。嵌套超超图使用来自迭代幂集的超顶点；超超边可以包含其他超超边，并通过秩排序以避免环 [109]。

2.11 多重超图与多重超超图

多重超图是一种允许重复超边的超图；边构成非空顶点子集的多重集，并带有重数计数 [110, 111]。已知多重超图同时推广了超图和多重图。多重超超图是一种允许重复超边的超超图；顶点是嵌套集合对象，且超边携带重数。

定义 2.11.1（多重超图）。[110, 111] 设 V 是一个有限非空集。记：

2.13 迭代全图

全图的顶点同时包含图的顶点和边，并通过邻接或关联关系将它们连接起来（参见 [127, 128]）。

2.14 层级超超图

层级超超图是一种超超图，其顶点存在于多个幂集层级上，允许边连接混合层级的超顶点，同时保持向下封闭一致性（参见 [131, 132]）。