大数据如何将图论带入新维度

作者:糖果
发布时间:2024-04-24 02:11:29 (12小时前)
来源:theory-into-new-dimensions-20210819/

讨论连接的数学语言通常取决于网络——顶点（点）和边（连接它们的线）——至少自 18 世纪以来一直是模拟现实世界现象的宝贵方法。但几十年前，巨大数据集的出现迫使研究人员扩展他们的工具箱，同时也为他们提供了广阔的沙箱，可以在其中应用新的数学见解。科罗拉多大学博尔德分校的计算机科学家Josh Grochow说，从那时起，随着研究人员开发了新型网络模型，可以在大数据的噪音中找到复杂的结构和信号，经历了一段激动人心的快速增长时期。
Grochow 是越来越多的研究人员之一，他们指出在大数据中寻找联系时，图论有其局限性。图将每一种关系表示为二元组或成对交互。然而，许多复杂的系统不能单独用二元连接来表示。该领域的最新进展显示了如何向前发展。
考虑尝试建立一个育儿网络模型。显然，每个父母都与孩子有联系，但养育关系不仅仅是这两个联系的总和，因为图论可能会对其进行建模。尝试模拟同伴压力等现象也是如此。
现在我们知道网络只是事物的影子。
Josh Grochow，科罗拉多大学博尔德分校
“有很多直观的模型。德国亚琛工业大学的Leonie Neuhäuser说，只有当你的数据中已经有群体时，才能捕捉到同伴压力对社会动态的影响。但是二元网络不能捕捉群体影响。
数学家和计算机科学家使用术语“高阶相互作用”来描述这些复杂的方式，即群体动态而不是二元联系可以影响个体行为。从量子力学中的纠缠相互作用到疾病在人群中传播的轨迹，这些数学现象无处不在。例如，如果药理学家想要模拟药物相互作用，图论可能会显示两种药物如何相互反应——但三种药物呢？还是四个？
虽然探索这些相互作用的工具并不新鲜，但直到最近几年，高维数据集才成为发现的引擎，为数学家和网络理论家提供了新的思路。这些努力已经产生了关于图的限制和扩展的可能性的有趣结果。
“现在我们知道网络只是事物的影子，”格罗乔说。如果数据集具有复杂的底层结构，那么将其建模为图形可能只能揭示整个故事的有限投影。
“我们已经意识到，我们用来研究事物的数据结构，从数学的角度来看，并不完全符合我们在数据中看到的情况，”太平洋西北国家实验室的数学家Emilie Purvine说。
这就是为什么数学家、计算机科学家和其他研究人员越来越关注如何推广图论——以它的多种形式——来探索高阶现象。过去几年提出了大量建议的方法来表征这些相互作用，并在高维数据集中用数学方法验证它们。
对于 Purvine 来说，高阶相互作用的数学探索就像是新维度的映射。“将图表视为二维土地的基础，”她说。可以登上顶部的三维建筑可能会有很大差异。“当你在地面上时，它们看起来是一样的，但你在上面建造的东西却不同。”
##### 进入超图
寻找那些更高维的结构是数学变得特别模糊和有趣的地方。例如，图的高阶类似物称为超图，它具有“超边”而不是边。这些可以连接多个节点，这意味着它可以表示多路（或多线性）关系。超边可能会被视为一个表面，而不是一条线，就像在三个或更多地方固定的防水布一样。
这很好，但我们仍然不知道这些结构与传统结构的关系。数学家目前正在学习哪些图论规则也适用于高阶交互，这表明了新的探索领域。
为了说明超图可以从大数据集（而普通图不能）中梳理出的关系类型，Purvine 举了一个离家很近的简单例子，即科学出版物的世界。想象两个数据集，每个数据集包含最多由三位数学家共同撰写的论文；为简单起见，我们将它们命名为 A、B 和 C。一个数据集包含六篇论文，三对不同的对（AB、AC 和 BC）各有两篇论文。另一篇总共只包含两篇论文，每篇论文都由三位数学家 (ABC) 共同撰写。
来自任一数据集的共同作者的图形表示可能看起来像一个三角形，表明每个数学家（三个节点）都与其他两个（三个链接）合作过。Purvine 说，如果你唯一的问题是谁与谁合作，那么你就不需要超图了
但是如果你有一个超图，你也可以回答关于不太明显的结构的问题。例如，第一组的超图（有六篇论文）可以包括显示每个数学家贡献四篇论文的超边。对两组超图的比较表明，论文的作者在第一组中不同，但在第二组中相同。
##### 野外超图
这种高阶方法已经被证明在应用研究中很有用，例如当生态学家展示了 1990 年代将狼重新引入黄石国家公园时，如何引发生物多样性和食物链结构的变化。在最近的一篇论文中，Purvine 和她的同事分析了一个对病毒感染的生物反应数据库，使用超图来识别所涉及的最关键的基因。他们还展示了图论提供的通常的成对分析是如何忽略这些相互作用的。
“这就是我们从超图中看到的那种超越图形的力量，”Purvine 说。
然而，从图泛化到超图很快变得复杂。说明这一点的一种方法是考虑图论中的规范切割问题，该问题询问：给定图上的两个不同节点，您可以切割的最小边数是多少以完全切断两者之间的所有连接？许多算法可以很容易地找到给定图的最佳切割次数。
但是如何切割超图呢？康奈尔大学的数学家Austin Benson说：“有很多方法可以将这种切割概念推广到超图。” 但是没有一个明确的解决方案，他说，因为可以通过各种方式切断超边，从而创建新的节点组。
Benson最近与两位同事一起尝试将分割超图的所有不同方法形式化。他们的发现暗示了各种计算复杂性：在某些情况下，问题很容易在多项式时间内解决，这基本上意味着计算机可以在合理的时间内处理解决方案。但对其他人来说，这个问题基本上是无法解决的——根本不可能确定是否存在解决方案。

“那里仍有许多悬而未决的问题，”本森说。“其中一些不可能的结果很有趣，因为你不可能将它们简化为图形。在理论方面，如果你还没有将它简化为你可以用图表找到的东西，它会告诉你那里有一些新东西。”
##### 数学三明治
 但是超图并不是探索高阶交互的唯一方法。拓扑——对在拉伸、压缩或以其他方式变换对象时不会改变的几何属性的数学研究——提供了一种更直观的方法。当拓扑学家研究网络时，他们会寻找形状、表面和尺寸。他们可能会注意到连接两个节点的边是一维的，并询问不同网络中一维对象的属性。或者他们可能会看到由三个节点连接而成的二维三角形表面并提出类似的问题。
拓扑学家称这些结构为单纯复合体。这些实际上是通过拓扑框架查看的超图。神经网络属于机器学习的一般类别，提供了一个有说服力的例子。它们由旨在模拟我们大脑神经元如何处理信息的算法驱动。图神经网络 (GNN) 将事物之间的连接建模为成对连接，擅长推断大型数据集中缺失的数据，但与其他应用程序一样，它们可能会错过仅由三个或更多组产生的交互。近年来，计算机科学家开发了单纯神经网络，它使用高阶复合物来概括 GNN 的方法来发现这些影响。
单纯复形将拓扑学与图论联系起来，并且像超图一样，它们提出了令人信服的数学问题，这将推动未来的研究。例如，在拓扑学中，单纯复形的特殊子集本身也是单纯复形，因此具有相同的性质。如果超图也是如此，则子集将包括其中的所有超边——包括所有嵌入的双向边。
但情况并非总是如此。“我们现在看到的是，数据落入了这个中间地带，在这个中间地带，不是每个超边，不是每个复杂的交互，都与其他每一个都一样，”Purvine 说。“您可以进行三向交互，但不能进行成对交互。” 大数据集清楚地表明，无论是在生物信号网络中还是在同伴压力等社会行为中，群体影响力往往远远超过个人的影响力。
Purvine 将数据描述为填充一种数学三明治的中间，上面受这些拓扑思想的约束，下面受图形的限制。网络理论家现在面临着寻找高阶相互作用的新规则的挑战。她说，对于数学家来说，“还有发挥的空间。”
##### 随机游走和矩阵
这种创造性的“游戏”感也延伸到其他工具。Benson 说，图表和其他用于描述数据的工具之间存在着各种美妙的联系。“但是一旦你进入更高阶的设置，这些联系就更难获得了。”
他说，当您尝试考虑马尔可夫链的高维版本时，这一点尤其明显。马尔可夫链描述了一个多阶段过程，其中下一阶段仅取决于元素的当前位置；研究人员使用马尔可夫模型来描述信息、能量甚至资金等事物如何在系统中流动。也许马尔可夫链最著名的例子是随机游走，它描述了一条路径，其中每一步都是从前一步随机确定的。随机游走也是一个特定的图：沿着图的任何游走都可以显示为沿着链接从一个节点移动到另一个节点的序列。
但是如何扩大像散步这样简单的事情呢？研究人员转向高阶马尔可夫链，它不仅取决于当前位置，还可以考虑许多以前的状态。事实证明，这种方法可用于对网络浏览行为和机场交通流量等系统进行建模。Benson 有其他扩展方法的想法：他和他的同事最近描述了一种用于随机或随机过程的新模型，该模型将高阶马尔可夫链与另一种称为张量的工具相结合。他们针对纽约市的出租车乘坐数据集对其进行了测试，以了解其预测轨迹的能力。结果喜忧参半：他们的模型比通常的马尔可夫链更好地预测了出租车的运动，但两种模型都不太可靠。
张量本身代表了另一种研究近年来已经出现的高阶相互作用的工具。要理解张量，首先要考虑矩阵，它将数据组织成行和列的数组。现在想象一下由矩阵组成的矩阵，或者矩阵不仅具有行和列，还具有数据的深度或其他维度。这些是张量。如果每个矩阵都对应于一个音乐二重奏，那么张量将包括所有可能的乐器配置。
张量对于物理学家来说并不是什么新鲜事，他们长期以来一直使用它们来描述例如粒子的不同可能量子态，但网络理论家采用这种工具来扩展矩阵在高维数据集中的能力。数学家们正在使用它们来解决新的问题。Grochow 使用张量来研究同构问题，它本质上是问你如何知道两个对象在某种程度上是否相同。他最近与乔有明的合作产生了一种新方法来识别可能难以或不可能解决的复杂问题。
##### 如何负责任地进行超图
Benson 不确定的出租车模型提出了一个普遍的问题：研究人员何时真正需要像超图这样的工具？在许多情况下，在合适的条件下，超图将提供与图完全相同类型的预测和分析。“如果某些东西已经封装在网络中，那么真的有必要将系统建模为 [作为高阶]吗？” 亚琛工业大学的Michael Schaub问道。
他说，这取决于数据集。“图是社交网络的一个很好的抽象，但社交网络远不止这些。对于高阶系统，有更多的建模方法。” 例如，图论可能会显示个人是如何联系在一起的，但无法捕捉社交媒体上的朋友群如何影响彼此的行为。
相同的高阶相互作用不会出现在每个数据集中，所以奇怪的是，新理论是由数据驱动的——这挑战了最初将 Purvine 吸引到该领域的潜在逻辑意义。“我喜欢数学的地方在于它以逻辑为基础，如果你遵循正确的方向，你就会得到正确的答案。但有时，当你定义全新的数学领域时，正确的方法是主观的，”她说。“如果你不承认有多种方法可以做到这一点，你可能会把社区推向错误的方向。”
Grochow 说，最终，这些工具代表了一种自由，不仅能让研究人员更好地理解他们的数据，还能让数学家和计算机科学家探索新的可能性世界。“有无穷无尽的东西可以探索。它既有趣又美丽，并且是许多重要问题的来源。”

1 条回复

动动手指，沙发就是你的了！

登录后才能参与评论