图论新维度：数据驱动的数学理论，揭秘复杂联系的新工具

作者 | Stephen Ornes

编译 | 王晔

校对 | 维克多

用由点和线组成的网络形式对现实世界建模，是自18世纪以来采用的主流方法。但随着大数据的出现，研究人员开发了更多的数学工具，在大量的计算机资源加持下，数学研究不断被发现。

正如科罗拉多大学博尔德分校的计算机科学家Josh Grochow说的那样：“整个领域经历了一个令人兴奋的快速增长期。”，“毕竟，新网络模型的出现，让我们有能力在大数据的噪音中找到有价值的东西：复杂的结构和信号。”

在之前，业界往往用数学分支中的图论表示两个事物中的关系。但当涉及到大数据时候，需要关系并不能用简单的二元关系来表示，换句话说，传统的图论思维表现出了“短板”。

例如尝试建立一个关于养育子女的网络模型。图论能表现出父母与孩子的联系，但是对于同侪压力等群体效应往往束手无措，即二元网络并不能捕捉到群体的影响。再例如，如果一位药理学家想模拟药物相互作用，图论可能会显示两种药物如何相互反应。但三种药物呢？或者四种呢？

对于群体效应等的描述，数学家和计算机科学家发明了"高阶互动 "一词。从量子力学中的相互作用到疾病在人群中传播的轨迹，这些"高阶互动 "的数学现象遍布各个方面。

最近几年，高维数据集成为探索的引擎，给数学家和网络理论家带来新思路。对于图论表示“高阶互动”有了新的研究成果。最直观的表现是一些数学家已经意识到：从数学角度来看，我们以为的数据结构并不完全适合我们在数据中看到的情况。

Emilie Purvine

"网络只是事物的影子，"Grochow表示。如果一个数据集有一个复杂的基础结构，那么把它作为一个图来建模可能只揭示了整个故事的有限投影。

1

进入超图（Hypergraph）

寻找高维结构使数学变得特别模糊而有趣。例如，图的“高阶类似物”被称为超图。结合图，可以理解到超图就是每一个边可以包含两个以上的点所构成的图，这意味着它可以代表多向（或多线性）关系。

超图的边（Hyperedge）可以被看作是一个表面，而不是一条线，就像在三个或更多地方钉了一块油布一样。

超图如何从大数据集中挖掘关系类型？以科学出版为例，想象两个数据集，每个数据集都包含最多由三位数学家共同撰写的论文；为了简便，我们把它们命名为A、B和C。一个数据集包含六篇论文，其中三个不同的二人合著组（AB、AC和BC）各写了两篇论文。另一个数据集只包含两篇论文，每篇都是由三位数学家合著的（ABC）。

从这两组数据中提取的合著关系图可能看起来像一个三角形，显示每个数学家（三个节点）都与另外两个数学家（三个链接）合作过。当然，如果只有“谁与谁合作”这一个问题，那么就不需要超图。

超图可以回答关于不明显结构的问题。例如，第一个数据集的超图（有六篇论文）可能包括显示每个数学家对四篇论文有贡献的超边。对两组超图的比较将表明，第一个数据集中的论文作者不同，但在第二个数据集中是相同的。

这种高阶方法在应用研究中已经被证明是有用的。例如，20世纪90年代，生态学家展示了向黄石国家公园重新引进狼群时，生物多样性和食物链结构的变化过程。在最近的一篇论文中，美国西北太平洋国家实验室的数学家milie Purvine和她的同事分析了一个病毒感染的生物反应数据库，使用超图来确定所涉及的最关键基因。在论文中，他们还展示了这些相互作用是如何被图论提供的通常成对分析遗漏的。

康奈尔大学的Austin Benson最近使用高阶马尔科夫链和张量模拟了纽约市的出租车行程。虽然仍有改进空间，但结果比传统的马尔科夫链要好。

然而，从图到超图的泛化很快就会变得复杂。例如图论中的规范切割问题，该问题问到："给定一个图上的两个不同的节点，你最少可以切割多少条边来完全切断两者之间的所有联系？给定一个图上的两个不同的节点，要完全切断这两个节点之间的所有联系，你能切断的最少的边数是多少？许多算法可以很容易地找到给定图形的最佳切割数。

但是如何切割超图呢？康奈尔大学的数学家Austin Benson说：“有很多方法可以将这种切割的概念推广到超图中。但没有一个明确的解决方案”，他说“因为超边可以以各种方式被切断，创造出新的节点组”。

最近，Benson 与两位同事一起，尝试将分割超图的所有不同方式正式化。但对于某些情况，这个问题基本上是无法解决，或者说无法确定是否存在解决方案。

2

数学三明治

超图并不是探索高阶互动的唯一方法。拓扑学是一种对几何属性的数学研究，其假设是：当你拉伸、压缩或以其他方式转换对象时，这些属性不会改变。拓扑学提供了一种更直观的方法。当拓扑学家研究一个网络时，他们寻找形状、表面和尺寸。他们可能会注意到连接两个节点的边是一维的，并询问不同网络中一维物体的属性。或者他们可能会看到连接三个节点所形成的二维三角形表面，并提出类似的问题。

拓扑学家把这些结构称为simplicial complexes。实际上，这是通过拓扑学的框架来看的超图，神经网络提供了一个很好的例子。它们由旨在模仿我们大脑的神经元如何处理信息的算法驱动。图形神经网络（GNNs）将事物之间的连接建模为成对连接，擅长推断大数据集中缺失的数据，但在其他应用中，它们可能会错过仅由三个或更多群体产生的相互作用。近年来，计算机科学家开发了simplicial neural networks，它使用高阶复数来概括GNN的方法，以求发现这些效应。

simplicial complexes 将拓扑学与图论联系起来，与超图一样，它们提出了引人注目的数学问题。例如，在拓扑学中，simplicial complexes 的特殊类型的子集本身也是simplicial complexes ，因此具有相同的属性。如果超图也是如此，子集将包括其中的所有超边——包括所有嵌入的双向边。

但情况并非总是如此。“我们现在看到的是，数据落入了中间地带，你可以进行三向互动，但不是成对的互动。”Purvine表示，“大数据集已经清楚地表明，无论是在生物信号网络中还是在同行压力等社会行为中，群体的影响往往远远超过个人的影响”。

Purvine将数据描述为数学三明治的中间部分，上限是拓扑学思想，下限是图论。

3

随机游走和矩阵

这种创造性的 "游戏 "感也延伸到了其他工具。在图和其他描述数据的工具之间存在着各种美妙的联系。但是一旦你转移到高阶设置，这些联系就难以出现了。当你试图考虑马尔科夫链的高维版时，这一点尤其明显。

马尔科夫链描述了一个多阶段的过程，其中下一阶段只取决于元素的当前位置；研究人员已经使用马尔科夫模型来描述信息、能量甚至金钱等事物如何在一个系统中流动。马尔科夫链最著名的例子也许是随机漫步，它描述了一条路径，其中每一步都是由之前的步骤随机决定的。随机漫步也是一个特定的图。任何沿着图的轨迹都可以显示为一个沿着链接从节点到节点的序列。

但如何扩大像步行这样简单的东西呢？研究人员转向高阶马尔科夫链，它不仅取决于当前的位置，还可以考虑许多以前的状态。这种方法已被证实对网络浏览行为和机场交通流等系统的建模非常有用。

Austin Benson

正如前文所言，Austin Benson最近描述了一个新的随机过程模型，该模型将高阶马尔科夫链与张量结合起来。用纽约市的出租车乘坐数据集对其进行了测试，以了解其预测轨迹的能力。结果是喜忧参半：模型对出租车运动的预测比通常的马尔科夫链要好，但这两个模型都不是很可靠。

张量本身是研究高阶相互作用的另一种工具，近年来已经开始发挥作用。要理解张量，首先考虑矩阵，它将数据组织成行和列的数组。现在想象一下由矩阵组成的矩阵，或者不仅有行和列，还有深度或其他维度的数据的矩阵。这些都是张量。如果每个矩阵都对应于一个音乐二重奏，那么张量将包括所有可能的乐器配置。

对物理学家来说，张量并不新奇，例如用来描述一个粒子的不同可能的量子态。但网络理论家采用这一工具来提高矩阵在高维数据集中的能力。

4

什么时候用超图？

前文所述，Benson不确定的出租车模型表现出一个普遍存在的问题：研究人员何时真正需要超图这样的工具？在许多情况下，如果条件合适，超图将提供与图完全相同的预测和分析。"亚琛工业大学的Michael Schaub问道："如果某些东西已经被封装在网络中，是否真的有必要对系统进行建模为高阶？

这取决于数据集，图是社交网络的一个很好的抽象，但社交网络是如此之多。对于高阶系统，有更多的方法可以建模。例如，图论可能会显示个人是如何连接的，但不能捕捉到社交媒体上的朋友群是如何影响彼此的行为的。

同样的高阶互动不会出现在每一个数据集中，所以奇怪的是，新理论是由数据驱动的：这挑战了数学的基本逻辑。

Purvine表示，"我喜欢数学的原因是它是基于逻辑的，如果你遵循正确的方向，你会得到正确的答案。但有时，当你定义整个数学的新领域时，会有一种主观性，即什么是正确的方法。"她说，"如果你不承认有多种方法，你可能会把社区推向错误的方向。"

但对工具的探索代表了一种自由，不仅允许研究人员更好地理解他们的数据，而且允许数学家和计算机科学家探索新的可能性世界。有无尽的东西可以探索，这很有趣，也很美妙，是很多伟大问题的来源。