大数据将图论带入新维度


我喜欢数学的原因是它基于逻辑,如果你遵循正确的方向,你就会得到正确的答案。但有时,当你定义全新的数学领域时,正确的方法存在主观性,如果你不认识到有多种方法可以做到这一点,你可能会将社区引向错误的方向。

最终,这些工具代表了一种自由,不仅让研究人员能够更好地理解他们的数据,还让数学家和计算机科学家探索新的可能性世界。

研究人员正在转向高阶相互作用的数学,以更好地对数据中的复杂连接进行建模。

用于谈论连接的数学语言通常依赖于网络——顶点(点)和边(连接它们的线)——至少自 18 世纪以来一直是模拟现实世界现象的宝贵方法。

但几十年前,巨型数据集的出现迫使研究人员扩展他们的工具箱,研究人员开发出新型网络模型:图论,可以在大数据的噪音中找到复杂的结构和信号,出现了一个令人兴奋的快速增长时期。

在寻找大数据中的联系时,图论有其局限性,图将每个关系表示为二元关系或成对交互。然而,许多复杂系统不能仅用二元连接来表示。

数学家和计算机科学家使用“高阶相互作用”一词来描述群体动态(而不是二元链接)影响个体行为的复杂方式。

从量子力学中的纠缠相互作用到疾病在人群中传播的轨迹,这些数学现象无处不在。

这就是为什么数学家、计算机科学家和其他研究人员越来越关注以多种形式推广图论的方法,以探索高阶现象。

超图
图的高阶类似物称为超图:它具有“超边”而不是边。它们可以连接多个节点,这意味着它可以表示多路(或多线性)关系。超边可能被视为一个表面,而不是一条线,就像固定在三个或更多位置的防水布一样。

数学家目前正在学习图论的哪些规则也适用于高阶相互作用,这提出了新的探索领域。

假设两个数据集,每个数据集包含最多三名数学家共同撰写的论文;为简单起见,我们将它们命名为 A、B 和 C。一个数据集包含六篇论文,其中三对不同的对(AB、AC 和 BC)各发表两篇论文。另一篇总共只包含两篇论文,每篇论文均由三位数学家 (ABC) 共同撰写。

来自任一数据集的共同作者的图形表示可能看起来像一个三角形,表明每个数学家(三个节点)都与其他两个(三个链接)合作。

如果你唯一的问题是谁与谁合作,那么你就不需要超图了,但如果你确实有超图,你也可以回答有关不太明显的结构的问题。例如,第一组的超图(包含六篇论文)可以包括超边,显示每个数学家对四篇论文做出了贡献。对两组超图进行比较会发现,第一组论文的作者不同,但第二组论文的作者相同。

这种高阶方法已经在应用研究中被证明是有用的,例如生态学家展示了 20 世纪 90 年代将狼重新引入黄石国家公园如何引发了生物多样性和食物链结构的变化。在最近的一篇论文中,Purvine 和她的同事分析了病毒感染的生物反应数据库,使用超图来识别所涉及的最关键的基因。他们还展示了图论提供的通常的成对分析如何忽略这些相互作用。

从图推广到超图很快就会变得复杂。说明这一点的一种方法是考虑图论中的规范切割问题,该问题提出:给定图上的两个不同节点,要完全切断两者之间的所有连接,可以切割的最小边数是多少?许多算法可以轻松找到给定图的最佳切割次数。没有一个明确的解决方案,因为超边可以通过各种方式被切断,从而创建新的节点组。

在某些情况下,问题很容易在多项式时间内解决,这基本上意味着计算机可以在合理的时间内处理解决方案。但对于其他人来说,这个问题基本上是无法解决的——根本不可能确定是否存在解决方案。

但超图并不是探索高阶交互的唯一方法。拓扑——对拉伸、压缩或以其他方式变换对象时不会改变的几何属性的数学研究——提供了一种更直观的方法。

拓扑
当拓扑学家研究网络时,他们会寻找形状、表面和维度。他们可能会注意到连接两个节点的边是一维的,并询问不同网络中一维对象的属性。或者他们可能会看到连接三个节点形成的二维三角形表面并提出类似的问题。

拓扑学家将这些结构称为单纯复形。实际上,这些是通过拓扑框架查看的超图。属于机器学习一般范畴的神经网络提供了一个生动的例子。它们由旨在模仿我们大脑神经元如何处理信息的算法驱动。

图神经网络 (GNN) 将事物之间的连接建模为成对连接,擅长推断大型数据集中缺失的数据,但与其他应用程序一样,它们可能会错过仅由三个或更多组产生的交互。近年来,计算机科学家开发了简单神经网络,它使用高阶复合体来推广 GNN 的方法来发现这些效应。

单纯复形将拓扑与图论联系起来,并且像超图一样,它们提出了引人注目的数学问题,这些问题将推动未来的研究。例如,在拓扑中,特殊类型的单纯复形子集本身也是单纯复形,因此具有相同的属性。如果对于超图来说同样如此,则子集将包括其中的所有超边——包括所有嵌入的双向边。

但情况并非总是如此:数据落入了这个中间地带,其中并非每个超边、不是每个复杂的交互都与其他每个超边的大小相同,你可以进行三向互动,但不能进行成对互动。大数据清楚地表明,无论是在生物信号网络还是在同伴压力等社会行为中,群体的影响力往往远远超过个人的影响力。

将数据描述为填充了一种数学三明治的中间,三明治上面顶部受到拓扑学思想的约束,而三明治底部则受到图的限制。

马尔可夫模型
也许马尔可夫链最著名的例子是随机游走,它描述了一条路径,其中每一步都是根据之前的一步随机确定的。随机游走也是一种特定的图:沿着图的任何游走都可以显示为沿着链接从一个节点移动到另一个节点的序列。

研究人员使用马尔可夫模型来描述信息、能量甚至金钱等事物如何在系统中流动。马尔可夫链描述了一个多阶段过程,其中下一阶段仅取决于元素的当前位置。

研究人员转向高阶马尔可夫链,它不仅仅依赖于当前位置,还可以考虑许多先前的状态,事实证明,这种方法对于网络浏览行为和机场交通流量等系统建模非常有用。

本森有其他方法来扩展它:他和他的同事最近描述了一种随机过程的新模型,该模型将高阶马尔可夫链与另一种称为张量的工具结合起来。他们根据纽约市的出租车出行数据集对其进行了测试,看看它预测轨迹的效果如何。结果好坏参半:他们的模型比通常的马尔可夫链更好地预测了出租车的运动,但这两个模型都不是很可靠。

张量
张量本身代表了近年来兴起的另一种研究高阶相互作用的工具。要理解张量,首先想到矩阵,它将数据组织成行和列的数组。

现在想象一下由矩阵组成的矩阵,或者不仅具有行和列,而且还具有数据的深度或其他维度的矩阵。这些是张量。如果每个矩阵都对应于一首音乐二重奏,那么张量将包括所有可能的乐器配置。

张量对于物理学家来说并不是什么新鲜事,他们长期以来一直使用张量来描述粒子的不同可能量子态,但网络理论学家采用这种工具来扩展高维数据集中矩阵的威力。数学家正在利用它们来解决新的问题。