当前位置: 首页 > 服务项目 > 大数据

图论是不够的,大数据借助高阶交互作用,将图论带入新维度

09-02
在寻找大数据中的关系时,图论有其局限性。图只能将每个关系表示为二元组,然而,许多复杂系统不能仅用二元连接来表示。在本文中研究人员转向高阶交互作用的数学,以更好地模拟数据中的复杂连接。

至少从 18 世纪开始,用数学方式的语言来讨论连接问题就一直是模拟真实世界现象的宝贵方法,这种描述方式取决于网络,它们具有顶点(点)和边(连接线)。但几十年前,大数据集的出现迫使研究者开始扩展工具箱,同时大数据集也为研究者提供了广阔的研究空间,可以在其中应用新的数学见解。自那时起,科罗拉多大学博尔德分校的计算机科学家 Josh Grochow 说,研究人员已经开发出一种新的网络模型,它可以在大数据的噪声中找到复杂的结构和信号。图论在复杂关系中的局限性Grochow 是众多研究人员中的一员,他们指出,在寻找大数据中的关系时,图论有其局限性。图将每个关系表示为二元组或成对交互。然而,许多复杂系统不能仅用二元连接来表示。现在我们尝试构建一个育儿网络模型,显然,每个父母都与孩子有联系,但养育关系并不像图论所描述的那样,只是两个关系的总和。同样的道理也适用于试图模拟类似同辈压力的现象。「目前有许多直观的模型,同辈压力对社交动态的影响只有在数据中已经有群体的情况下才会被捕捉到,」亚琛工业大学的 Leonie Neuhäuser 说道。但二元网络无法捕捉到群体影响。数学家和计算机科学家使用术语「高阶交互」来描述这些复杂的方式,即群体动态而不是二元联系可以影响个体行为。从量子力学中的纠缠交互到疾病在人群中传播的轨迹,这些数学现象无处不在。例如,如果药理学家想要模拟药物相互作用,图论可能会显示两种药物如何相互反应——但三种药物、 四个药物之间的相互反应如何呢?虽然探索这些交互作用的工具并不新鲜,但直到最近几年,高维数据集成为发现事物的引擎,为数学家和网络理论家提供了新的思路。这些努力已经产生了关于图的限制和可扩展的有趣结果。「现在我们知道网络只是事物存在方式的某种影子,」Grochow 说。如果数据集具有复杂的底层结构,那么将其建模为图,可能只会揭示整个故事的有限投影。「我们已经意识到用来研究事物的数据结构,从数学的角度来看,并不完全符合我们在数据中看到的情况,」来自美国西北太平洋国家实验室的数学家 Emilie Purvine 说道。

Emilie Purvine。图源:Andrea Starr/Pacific Northwest National Laboratory这就是为什么数学家、计算机科学家和其他研究人员越来越关注图论以及它的多种形式,并利用图论来探索高阶现象。过去几年研究人员提出了大量方法来表征这些交互作用,并在高维数据集中用数学方法验证所提方法。超图寻找那些高维结构会使数学变得既模糊又有趣。例如,图的高阶类似物称为超图,它具有「超边,hyperedges」而不是边。它们可以连接多个节点,这意味着它可以表示多路(或多线性)关系。超边可能会被视为一个表面,而不是一条线。那么这些结构如何关联到它们的传统对照物,目前我们依然有很多不了解的细节。不过数学家正在学习哪些图论规则也适用于高阶交互,这为探索新的领域提供了思路。为了证明超图可以从大型数据集中梳理出这种关联而普通图没有这种能力,Purvine 举了一个简单示例——科学出版物。假设有两个数据集,每个数据集都包含最多 3 名数学家合著的论文,将他们称为 A、B 和 C。其中一个数据集包含 6 篇论文,3 位数学家两两组合(AB、AC 和 BC)各有两篇论文;另一个数据集只有 2 篇论文,每篇论文都有 3 位数学家合著(ABC)。每个数据集中合著关系图看起来像是三角形,表示每位数学家(3 个节点)都与其他两位(3 个链接)具有合作关系。如果你只想问「谁和谁合著」,则不需要使用超图。但如果你使用了超图,也可以回答结构不太明显的问题。比如,上文中第一个数据集(6 篇论文)的超图包含了每位数学家对 4 篇论文做出贡献的超边。并且,比较两个数据集的超图可以发现,第一个数据集中论文作者不同,第二个数据集中论文作者相同。超图的超边切割这种高阶方法已被证明在应用研究中有用,比如 20 世纪 90 年代生态学家展示了在黄石公园引入狼群改变了生物多样性和食物链结构。在最近的一篇论文中,Purvine 及其同事分析了病毒性感染的生物响应数据集,其中使用超图来识别最临限的基因。他们还展示了常见的图论成对分析中遗漏了这些交互。Purvine 表示:「这就是我们正在从超图中看到的力量,超越了图。」但是,从图快速地泛化至超图就复杂了。证明这点的一种方式是思考图论的典型切割问题,也就是:给定图上的两个不同节点,为了完全断绝两个节点之间的所有关系,你能切割的最少边是多少?很多算法能够轻松地找出给定图的最佳切割边数量。切割超图会是什么情况呢?康奈尔大学助理教授、数学家 Austin Benson 表示:「我们可以使用很多方法将切割概念泛化至超图,但没有一种明确的解决方案,因为超边可以通过各种方式被切割,从而产生了新的节点组。」

Austin Benson。最近,Benson 和他的两位同事一起尝试将切割超图的所有不同方法进行形式化。他们发现不同的形式化暗示了各种计算复杂性:在一些情况下,该问题可以在多项式时间内轻松地解决,这意味着计算机可以在合理的时间内生成解决方案。但在另一些情况下,该问题基本上无法解决,这是因为不可能确切地知道是否存在一种解决方案。Benson 表示:「还有很多尚待解决的问题。其中一些不可能性结果(impossibility results)很有趣,因为你无法将它们简化成图。从理论角度看,如果你还没有将这些结果简化成一些利用图发现的东西,则意味着你可以获得一些新的东西。」数学三明治效应然而,超图并不是探索高阶交互的唯一方法。拓扑学是对「拉伸、压缩或变换物体时都不会改变的几何性质」的数学研究,为探索高阶交互提供了一种更直观的方法。当拓扑学家研究一个网络(network)时,他们会寻找形状、表面和维数。拓扑学家可能会注意到连接两个节点的边是一维的,并询问一维物体在不同网络中的属性。他们也可能发现连接三个节点形成的二维三角曲面,并询问类似的问题。拓扑学家将这些结构称为单纯复形(Simplicial Complex),它们是通过拓扑框架观察到的超图。归入机器学习(ML)一般范畴的神经网络提供了一个有说服力的例证。神经网络受到设计用于模拟人类大脑神经元处理信息的算法的驱动。将两种事物之间的交互建模为成对连接的图神经网络(GNN)擅长推理大型数据集遗漏的数据,但与在其他应用上一样,图神经网络可能会错过三个或以上组才能产生的交互。2020 年 12 月,瑞士联邦理工学院的计算机科学家已经开发出了简单神经网络( Simplicial Neural Networks),这种网络使用高阶复合体来泛化 GNN 方法,以发现以上效应。

论文地址:https://arxiv.org/pdf/2010.03633.pdf单纯复形将拓扑学与图论关联了起来,并且像超图一样,简单复形提出了可以推动未来研究的数学问题。例如,在拓扑学中,单纯复形的某些子集也是单纯复形,因而具备相同的属性。如果超图同样如此,则子集将包含所有的超边以及所有嵌入的双向边。然而,情况并非如此。Purvine 表示:「我们现在看到的情况是——数据陷入了中间地带,其中并不是每个超边或每个复杂交互都与其他超边或其他复杂交互具有相同的大小。你可以拥有一种三向交互,但不会产生成对交互。」大型数据集已经清楚地表明,不管是在生物信令网络还是在同辈压力等社交行为中,组群的影响通常远远大于个体的影响。Purvine 使用数据来填补数学三明治的中间部分,上面是拓扑学思想,下面是图的局限性。现在,网络理论学家面对的挑战是找到高阶交互的新规则。并且,她认为,数学家还有发挥的空间。随机游动和矩阵这种创造性的「发挥」也可以扩展至其他工具。Benson 表示:「图与其他描述数据的工具之间存在各种美妙的关系。但只要你切换到高阶设置,这些关系更加难以获得。」Benson 认为,当你尝试考虑高维版本的马尔可夫链(Markov chain)时,这一点尤为明显。马尔可夫链描述了一种多段过程,其中下一阶段仅仅依赖元素(element)的当前位置。研究者已经使用马尔可夫模型来描述信息、能量甚至金钱在系统中流动的方式。但是如何扩大像散步这样简单的事情呢?研究人员转向高阶马尔可夫链,它不仅取决于当前位置,还可以考虑许多以前的状态。事实证明,这种方法可用于对网络浏览行为和机场交通流量等系统进行建模。Benson 有其他扩展方法的想法:他和他的同事最近描述了一种用于随机或随机过程的新模型,该模型将高阶马尔可夫链与另一种称为张量的工具相结合。他们针对纽约市的出租车乘坐数据集对其进行了测试,以了解其预测轨迹的能力。结果喜忧参半:他们的模型比通常的马尔可夫链更好地预测了出租车的运动,但两种模型都不太可靠。张量本身代表了另一种研究近年来已经出现的高阶相互作用的工具。要理解张量,首先要考虑矩阵,它将数据组织成行和列的数组。现在想象一下由矩阵组成的矩阵,或者不仅有行和列,而且还有深度或其他维度的数据的矩阵,这些是张量。如果每个矩阵都对应于一个音乐二重奏,那么张量将包括所有可能的乐器配置。张量对物理学家来说并不是什么新鲜事,他们长期以来一直使用它们来描述例如粒子的不同可能量子态,但网络理论家采用这种工具来扩展矩阵在高维数据集中的能力。数学家们正在使用它们来解决新的问题。Grochow 使用张量来研究同构问题,它本质上是问你如何知道两个对象在某种程度上是否相同。他最近与乔有明的合作产生了一种新方法来识别可能难以或不可能解决的复杂问题。如何绘制超图Benson 不确定出租车模式,然后提出了一个普遍的问题:研究人员何时真正需要像超图这样的工具?在适当的情况下,超图将提供与图完全相同类型的预测和分析。对于社交网络来说,图是一个很好的抽象概念,但社交网络远不止如此。对于高阶系统,有更多的建模方法。例如,图论可以显示个体之间的联系,但无法捕捉社交媒体上的朋友群是如何影响彼此行为的。同样的高阶交互作用不会出现在每个数据集上,所以奇怪的是,新的理论是由数据驱动的。「我喜欢数学的地方在于它以逻辑为基础,如果你遵循正确的方向,你就会得到正确的答案。但有时,当你定义全新的数学领域时,正确的做法是主观的,」Purvine 说。「如果你不承认有多种方法可以做到这一点,你可能会把社区推向错误的方向。」最后,这些工具代表了一种自由,不仅是让研究人员可以很好的了解数据,还能让数学家和计算机科学家探索新的世界。这有无穷无尽的内容值得探索。它很有趣也很漂亮,是激发许多伟大问题的来源。原文链接:https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/

免责声明:本站部分内容来源于互联网。如果本站部分内容侵犯您的权益,请您告知,站长会立即处理,联系方式见网站底部。

点击排行

编辑推荐