导语
图论是模拟现实世界网络结构的有效工具。但在寻找大数据之间的联系时，图论有其局限性，许多复杂系统不能只用成对的连接来表示。要如何扩展图论，揭示其无法捕捉到的高阶相互作用呢？科学家们发展出超图，甚至引入拓扑学、马尔可夫链、张量等数学工具，来探索广阔的数据世界。
研究领域：网络，图论，超图，拓扑，马尔可夫链，张量
Stephen Ornes | 作者
梁金 | 译者
刘培源 | 审校
邓一雪 | 编辑
数学中通常用网络来讨论连接问题，网络由顶点和连接顶点的边组成。至少从18世纪开始，网络就成为模拟现实世界的有效方法。但几十年前，巨大数据集的出现迫使研究人员扩展他们的工具箱，同时也为他们提供了庞大的沙盒来应用新的数学见解。科罗拉多大学博尔德分校的计算机科学家 Josh Grochow 说，从那以后，随着研究人员发展出新的网络模型，可以在大数据的噪音中找到复杂的结构和信号，出现了一个令人兴奋的快速增长期。 不过，Grochow 和越来越多的研究人员发现，在寻找大数据之间的联系时，图论有其局限性 。图将每一种关系表示为二元组 （dyad） 或成对的交互。然而，许多复杂系统不能只用成对的连接来表示 。例如，要建立一个关于养育关系的网络模型时，显然，每个父母都与孩子有联系，但养育关系并不像图论可能模拟的那样，仅仅是这两种联系的总和。模拟类似同辈压力的现象时，也会遇到同样的问题。 “有很多直观的模型。只有在数据中已经有了群体 （group） 的情况下，同辈压力对社会动力学的影响才能被捕捉到。”德国亚琛工业大学的Leonie Neuhäuser说道。但二元网络无法捕捉到群体的影响 。 数学家和计算机科学家使用“高阶相互作用” （higher-order interaction） 这个术语，来描述群体动力学 （而非二元连接） 影响个体行为的复杂方式。从量子力学中的纠缠，到疾病在群体中的传播轨迹，这类数学现象随处可见。例如，如果一个药理学家想要建立一个关于药物间相互作用的模型 [1]，图论可能会显示两种药物如何相互作用——但如果是3种、4种药物呢？ 虽然探索这些相互作用的工具并非新鲜事物，但直到最近几年，高维数据集才成为发现的引擎，给数学家和网络科学家带来新想法。这些努力已经产生了有趣的结果，关于图的极限和扩展图论的可能性。 Grochow说，“现在我们知道网络只是它的影子。”如果一个数据集有复杂的底层结构，那么将其建模为一个图，可能只会揭示出整个图景的一个有限投影。 太平洋西北国家实验室 （Pacific Northwest National Laboratory） 的数学家 Emilie Purvine 说：“我们意识到，从数学的角度来看，用来研究事物的数据结构与从数据中看到的现象不太相符。” 这就是为什么数学家、计算机科学家和其他研究人员越来越关注以多种形式推广图论的方法，以探索高阶现象。在过去几年里，人们提出了大量方法来描述这些相互作用，并在高维数据集中对其进行数学验证。 对Purvine来说，对高阶相互作用的数学探索就像新维度的映射。她解释说，可以将图想象为一块二维土地，在这个平面上可以建造的三维建筑会非常不同。在地面上看来，它们似乎是一样的，但在上面建造的东西是不同的。 图1. 超图等工具能够绘制数据点之间的微妙联系，这令太平洋西北国家实验室的 Emilie Purvine 感到兴奋不已。| 来源：Andrea Starr/太平洋西北国家实验室
在寻找高维结构的过程中，数学变得特别模糊和有趣。例如，图的高阶类似物被称为超图 （hypergraph） ，它有“超边” （hyperedge） 而不是边。超边可以连接多个节点，这意味着它可以表示多路 （或多线性） 关系。边可以看作是一条线，而超边可以看作是一个面，就像一块防水布钉在三个或更多地方。 不过，关于超图与传统的图之间的关系，仍有很多未知。数学家们目前正在研究，图论中的哪些规则也适用于高阶相互作用，这为探索新领域提供了思路。 超图可以从大数据集中梳理出普通的图无法梳理出的关系 ，为了说明这一点，Purvine 举了科学出版领域的一个简单例子。假设有两个数据集，每个数据集包含三名数学家 （不妨命名为A、B、C） 合著的论文。其中一个数据集包含6篇论文，三对 （AB、AC和BC） 中的每一对都有两篇论文。另一个数据集总共只有两篇论文，每一篇都由三位数学家 （ABC） 共同撰写。 从任意一个数据集中提取的表示合作关系的图，看起来可能都像一个三角形，表明每个数学家 （3个节点） 都与其他两个合作过 （3个连接） 。Purvine说，如果唯一的问题是谁与谁合作，那就不需要超图。 但如果有了超图，就可以看到一些不太明显的结构。例如，第一个数据集 （包含6篇论文） 的超图可能有一些超边，表明每个数学家贡献了4篇论文。比较两个数据集的超图可以发现，第一组论文的作者不同，而第二组的作者相同。
这种高阶方法在应用研究中已经被证明是有用的。例如生态学家已经展示，20世纪90年代向黄石国家公园中重新引入狼，如何引发了生物多样性和食物链结构的变化。在最近一篇论文中，Purvine 和同事分析了一个关于病毒感染的生物反应的数据库，使用超图来识别最关键的基因[2]。他们还表明，图论通常提供的成对分析怎样遗漏掉了这些相互作用。Purvine说：“这就是我们从超图中看到的力量，超图超越了图。” 然而，从图推广到超图很快就变得复杂起来 。说明这一点的一种方法是，考虑图论中的正则切割问题 （canonical cut problem） ，即：给定图上两个不同的节点，要完全切断这两个节点之间的所有连接，可以切割的最小边数是多少？对于一个给定的图，许多算法可以很容易地找到最佳切割数。 但是如何切割超图呢？康奈尔大学的数学家Austin Benson说，有很多方法可以将切割的概念推广到超图，但目前还没有一个明确的解决方案，因为超边可以通过多种方式被切断，产生新的节点群。 最近，Benson和两位同事一起，试图给出切割超图的所有不同方法 [3]。他们的发现暗示存在各种各样的计算复杂性：在某些情况下，问题很容易在多项式时间内解决，这基本上意味着计算机可以在合理的时间内给出解决方案。但在另一些情况下，问题基本上是无法解决的，甚至根本不能确定是否存在一个解决方案。 Benson说：“仍然有许多悬而未决的问题。有些不可能的结果很有趣，因为你不可能将超图简化成图。从理论方面来说，如果没有把它简化成可以用图找到的东西，就意味着那里有新东西。”
但超图并不是探索高阶相互作用的唯一方法，拓扑学提供了一种更直观的方法 。拓扑学是一个数学分支，研究当拉伸、压缩或使物体变形时那些保持不变的几何属性。当拓扑学家研究一个网络时，他们寻找形状、表面和维度。他们可能会注意到，连接两个节点的边是一维的，并追问不同网络中一维物体的性质。或者，他们可能会看到由三个节点连接而成的二维三角形表面，并提出类似的问题。 拓扑学家称这些结构为单纯复形 （simplicial complex） [4]，实际就是通过拓扑的框架来观察超图。机器学习中的神经网络提供了一个很好的例子。神经网络由模拟大脑神经元处理信息的算法驱动。图神经网络 （Graph neural networks, GNNs） 将事物之间的连接建模为成对连接，擅长推断大数据集中缺失的数据，但就像在其他应用中一样，它们可能遗漏掉由三个或更多节点组成的群体才会产生的相互作用。近年来，计算机科学家发展了单纯型神经网络 （Simplicial neural networks） [5]，使用高阶复形拓展了图神经网络方法，以找到这些高阶相互作用。 单纯复形将拓扑学与图论联系起来 ，而且像超图一样，它们提出了引人注目的数学问题，将推动未来的研究。例如，在拓扑学中，单纯复形的特殊类型的子集本身也是单纯复形，因此具有相同的性质。如果对超图也是如此，那么子集将包括其中的所有超边——包括所有嵌入的双向边。 但情况并非总是如此。Purvine说：“我们现在看到的是，数据处于中间地带，不是每一个超边，不是每一个复杂相互作用都是相同大小。你可以有三方互动，却不能有成对互动。”大数据集清楚表明，无论是在生物信号网络，还是同辈压力等社会行为中，群体的影响往往远超个人的影响。 Purvine 将数据描述为数学三明治的中间部分，上面是拓扑思想，下面是图论的限制 。网络科学家现在面临着为高阶相互作用寻找新规则的挑战。Purvine说，对于数学家来说，“还有了发挥的空间。”
这种发挥创造性的空间也可以延伸到其他工具。Benson说，在图和其他描述数据的工具之间存在各种美妙的联系，“但一旦进入更高阶的环境，就很难建立起这种联系”。 当尝试考虑高维版本的马尔可夫链时，这一点尤其明显。马尔可夫链 描述一种多阶段的过程，其中下一阶段只取决于元素当前的位置；研究人员使用马尔可夫链来描述信息、能量甚至金钱在系统中的流动。马尔可夫链最著名的例子也许是随机游走 （random walk） 。随机游走过程中，每一步由前一步随机决定。随机游走也是一种特定的图：图上的任何游走都可以表示为，沿着边从一个节点移动到另一个节点的序列。 但要如何从随机游走这样简单的事情延伸出去呢？研究人员转向高阶马尔可夫链，它不是仅仅依赖于当前的位置，而是可以考虑许多之前的状态。这种方法被证明对网络浏览行为和机场交通流等系统建模有用。 Benson还有其他扩展方法：他和同事最近描述了一种新的随机过程模型 [6]，将高阶马尔可夫链和张量（tensor）这种数学工具结合在一起 。 他们用这种方法对纽约市出租车行驶数据集进行了测试，看能否良好地预测轨迹。结果好坏参半：新模型比一般的马尔可夫链更好地预测了出租车的运动，但两种模型都不是很可靠。 图2. 康奈尔大学的 Austin Benson 最近利用高阶马尔可夫链和张量，帮助模拟了纽约市的出租车出行。结果比传统的马尔可夫链要好，但仍需改进。| 来源：Austin Benson
张量本身是研究高阶相互作用的另一种工具，近年来开始发挥重要作用。要理解张量 ，首先可以思考矩阵，矩阵将数据按照行和列排列；然后想象由矩阵组成的矩阵，或者矩阵不仅有行和列，还有深度或其他维度的数据——这就是张量。如果说矩阵对应音乐中的二重奏，那么张量将包括乐器的所有可能配置。 对物理学家来说，张量并不新鲜，他们一直用张量来描述一个粒子的不同可能量子态之类的现象，但网络科学家用这个工具将矩阵的力量扩展到高维数据集中 。数学家用它们解决新的问题。Grochow 用张量来研究同构问题 （isomorphism problem） ，同构问题本质上是追问，如何知道两个物体在一定程度上是否相同。他最近与 Youming Qiao 的合作提供了一种新方法 [7]，来识别也许很难或不可能解决的复杂问题。 Benson 关于纽约出租车的模型提出了一个普遍问题：研究人员什么时候真正需要超图这样的工具？ 在许多情况下，如果条件合适，超图将给出与图完全同样类型的预测和分析。“如果某些东西已经封装在网络中，真的有必要对系统进行 （高阶） 建模吗？”亚琛工业大学的 Michael Schaub 问道。 这取决于数据集。Schaub 说：“对于社交网络，图是一个很好的抽象描述，但社交网络远不止于此。对于高阶系统，有更多的建模方法。”例如，图论可以显示个体之间的联系，但无法捕捉社交媒体上的朋友群体如何影响个体的行为。 同样的高阶相互作用不会出现在每个数据集上，所以奇特的是，新理论是受数据驱动的 ——这挑战了最初吸引 Purvine 进入这一领域的底层逻辑。她说：“我喜欢数学是因为它是基于逻辑的，如果沿着正确的方向，就会得到正确的答案。但有时，当你定义一个全新的数学领域时，关于什么是正确的方法会存在主观性。如果没有认识到有多种方式可以做到这一点，就可能把研究引向错误的方向。” Grochow 说，最终，这些工具代表了一种自由，不仅允许研究人员更好地理解他们的数据，而且允许数学家和计算机科学家探索充满可能性的新世界。“有无尽的东西可以探索，这既有趣又美丽，并且是许多伟大问题的来源。” [1] Tekin, E., White, C., Kang, T.M. et al. Prevalence and patterns of higher-order drug interactions in Escherichia coli. npj Syst Biol Appl 4, 31 (2018). https://doi.org/10.1038/s41540-018-0069-9 [2] Hypergraph Models of Biological Networks to Identify Genes Critical to Pathogenic Viral Response. https://arxiv.org/abs/2010.03068 [3] Hypergraph Cuts with General Splitting Functions. https://arxiv.org/abs/2001.02817 [4] Simplicial complexes and complex systems. Vsevolod Salnikov et al 2019 Eur. J. Phys. 40 014001. https://iopscience.iop.org/article/10.1088/1361-6404/aae790/meta [5] Simplicial Neural Networks. https://arxiv.org/pdf/2010.03633.pdf [6] The Spacey Random Walk: A Stochastic Process for Higher-Order Data. https://doi.org/10.1137/16M1074023 [7] On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. https://drops.dagstuhl.de/opus/volltexte/2021/13570/
https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/
集智斑图顶刊论文速递栏目上线以来，持续收录来自Nature、Science等顶刊的最新论文，追踪复杂系统、网络科学、计算社会科学等领域的前沿进展。现在正式推出订阅功能，每周通过微信服务号「集智斑图」推送论文信息。扫描下方二维码即可一键订阅：
点击“阅读原文”，追踪复杂科学顶刊论文