ACM通信
新闻
一群努力
图片来源:马克斯·普朗克研究所
50年前，数学家保罗·厄兹在他的一次定期茶会上向朋友们提出了一个问题。三人本以为当天下午就能想出解决办法。
其他数学家花了49年的时间才给出答案。
Erds-Faber-Lovász猜想关注的是数学中一个熟悉的问题，即图着色问题。然而，这不是在一个传统的图表上，而是在另一个更复杂的结构上:超图。与图不同，图中节点之间的连接或边是点对点连接，超图的边可以包含任意数量的点。组可以重叠甚至包围其他组，因此有助于确保解决任何着色问题的因素，包括Erds设置的因素，与传统图的因素有很大不同。
这种差异实际上延续到了超图数学的所有其他方面。在这两种类型的结构之间有许多相似之处:完全有可能将传统图视为更丰富的超图家族的特殊情况。它本质上是一种超图，在这种情况下，每条边只允许跨越两个顶点。超图的多样性带来了更大的挑战，数学家们正试图在多个方面解决这些问题。
数字有7个顶点和4条边的超图。
当试图概括超图的性质时，“一切都是令人惊讶的，”德国莱比锡马克斯·普朗克科学数学研究所的组长Raffaella Mulas说。“当一件事情可以普遍化时，通常会让人感到惊讶，而当看起来微不足道的事情不能普遍化时，我也会感到惊讶。”
Mulas目前的研究领域主要集中在超图光谱。这些谱，就像图的谱一样，是由矩阵的转置和其他描述顶点连接方式的操作生成的。然而，这就是大部分相似之处。
在一个图中，矩阵对角线两边的边都由非零权值表示:行和列都表示顶点。
当用矩阵表示时，超图具有完全不同的结构。通常，顶点列在行中，每个边组都有自己的列。这反过来又引出了不同的机制，不仅用于构造光谱，还用于确定诸如特征值等派生性质的含义。
光谱是机器学习中的聚类等应用的重要工具，因为在原则上，它们提供了在数据中找到自然分组的计算成本较低的方法。通过关注由共享边数量判断的顶点之间的连通性，谱聚类在寻找分区方面可以被证明比k-means聚类等更简单的方法更有效。
Mulas说:“频谱可以为一个图做的最基本的事情是计算连接分量”，但这对超图不起作用。“只有在非常结构化的情况下，才能恢复超图的连通性谱。”
这些差异延缓了人们接受超图作为分析数据的工具，尽管在很多情况下，超图是最自然的表示。例如，在20世纪90年代初，理查德·史(Richard Shi)，当时是加拿大滑铁卢大学的博士后研究员，现在是西雅图华盛顿大学的电气工程教授，提出使用有向超图来构建集成电路的布局工具，使相关组件更紧密地连接在一起。
史宗伟构想的超图后来发展成为现在所知的定向超图，其中包括化学超图，之所以这样命名是因为它们可以很容易地表示使用催化剂的反应，以及另一种有实际重量的超图。Mulas已经与其他团队合作开发了工具，利用真实体重的变化来模拟生物间的相互作用。
近年来，超图已经成为解释社交网络中的行为和联系的焦点，因为它们可以显示比简单的成对关系更多的群体活动类型。然而，在处理大量数据时，分析组和简化结构以减少处理时间的可用工具仍然不足。由于图和超图之间的数学差异，过去的应用研究常常不得不依赖于图论中更成熟的工具，通常借助诸如团和星形扩展之类的扩展。
史所设想的超图后来演变成有向超图，其中包括化学超图和有实际权重的超图。
2006年，加州大学圣地亚哥分校的Sameer Agarwal和他的同事展示了几种被提出用于处理超图的高阶结构的算法，它们实际上使用了与普通图论相同的技术，所以使用它们几乎没有实际的好处。他们认为，用于机器学习的技术主要被简化为基于图的技术，尽管他们可能会使用诸如小团体之类的扩展来试图表示群体联系。
德州农工大学(Texas A&M University)计算机科学与工程学助理教授内特·维尔德(Nate Veldt)认为，2006年论文中确定的技术仍应被视为有用的超图技术。他指出:“明确地将高阶关系作为超边缘处理，往往会产生一些技术，如果你直接在图表中使用成对关系，可能无法获得这些技术，我认为这可以用于之前的这些方法。”他补充说，在这15年期间，情况已经发生了变化。
Veldt说:“最近关于超图分析的许多结果并不是简单地在应用一个简单的小团体或星形扩展之后再应用图方法。”“这些简单的简化技术在某些应用中确实表现良好，但我们也看到越来越多的例子和应用中，更复杂的分析超图的方法产生了更好的结果。”
Veldt和康奈尔大学的同事们开发了基于超图的聚类方法，他说，在一些任务中，比如在使用可穿戴设备收集邻近数据的实验中，识别小学和高中学生的分组，这种方法优于更简单的图化方法。
虽然他说这很难量化，但Veldt认为在过去的五年里超图研究有了加速发展。不同的小组正在研究各种核心数学和应用数学方面的问题。美国国家科学基金会(National Science Foundation)希望大数据应用能够受益，因此在去年向几位研究部分超图分析方法的研究人员提供了资助:这将允许它们在从存储中流出来时进行处理，而不是要求首先将整个结构加载到内存中。
一种更传统的减少大图计算负荷的方法是稀疏化。米兰博科尼大学(Bocconi University)计算机科学教授Luca Trevisan目前的研究重点是，稀疏化是一种通过移除顶点或边来简化图的方法，从而可以用更少的计算来分析它们的结构。他说，与旧的聚类算法一样，超图稀疏化需要依赖于图的约简方法。Trevisan的目标是发展利用张量的技术，可以产生更好的结果，并匹配现有的图稀疏器的性能。
虽然单个矩阵可以表示超图的连接，但将其转换为多维张量应该可以提供更全面地探测该结构的机会。穆拉斯说，停留在矩阵领域会导致有用信息的丢失。
去年，美国国家科学基金会(National Science Foundation)向几位研究人员授予了研究部分超图分析方法的经费。
将超图的数学转化为张量的一个大问题是，利用矩阵开发的线性代数工具常常会失效。在2013年的一篇论文中，伯克利数学科学研究所的Christopher Hillar和芝加哥大学的Lek-Heng Lim得出结论，在矩阵领域中，许多相对简单和高效的操作，如计算本征值，即使应用于只有三维的张量，也会变得NP-hard。
“我个人认为我对超图稀疏化的研究是一次侦察探险，是一种探索当你拥有传统线性代数技术无法解决的高维数据时该做什么的方法，”Trevisan说。“我喜欢超图稀疏化的问题，因为它让我在一个非常狭窄和清晰的特殊情况下进行探索。”
除了可能导致张量数学的基本进步外，超图分析在社会分组等应用中的使用也揭示了对数据结构的新见解。Veldt指出了同质性的概念:具有相似属性的节点被连接的趋势。图论中出现了各种同质性的定义，它们似乎与人们对社会群体的看法很好地联系在一起。然而，Veldt和康奈尔大学的同事们发现，不同类型的同质性不可能在同一个超图中共存:例如，男性和女性似乎无法同时表现出对性别占多数的群体的偏好。
Veldt说:“同质性的直观概念已经应用到图中，但在超图中并不适用。”
在超图环境中分析同质性可能需要不同的结构。“超图中的同质性可能不是你一开始想的那样。意识到这些潜在的数学必然性是很重要的并不一定是因为社会现象。我们的研究结果在精神上与“友谊悖论”相似:“你的朋友通常比你有更多的朋友”。这似乎与一种潜在的社会现象有关，但事实证明，这可以用图表中的事实组合来解释。”
进一步的工作将需要探索这两种表示之间的明显差异的理论基础，不仅是同质性，而且是超图的许多其他性质，以及它们如何影响应用。“理论带来了应用。并在应用中提出了该理论。两者相互激励，”穆拉斯说。
Erds和他的朋友们发现，开发一个类似于图表的知识体系需要多长时间，目前还不清楚。
进一步的阅读
阿加瓦尔，肯塔基州布兰森和贝隆吉。
图的高阶学习第23届机器学习国际会议论文集(ICML 2006),页面17-24
Jost, J.和Mulas, R。
实系数超图的归一化拉普拉斯算子复杂网络学报，第9卷第1期，2021年2月，cnab009
希拉，c.j.，林，l.h。
大多数张量问题都是np难的美国计算机学会杂志第45条，2013年11月，第60、6条
N. Veldt, A.R. Benson和J. Kleinberg。
高阶同质性是组合上不可能的arXiv: 2103.11818 (2021)，https://arxiv.org/abs/2103.11818
©2022 0001 - 0782/22/3 ACM
如果您不是为了盈利或商业利益而制作或分发本作品的部分或全部，并在第一页注明本通知和完整引用，则允许您免费制作本作品的部分或全部数字或纸质副本，供个人或课堂使用。本作品的组成部分必须由ACM以外的其他人享有版权。信用文摘是允许的。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org或传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM股份有限公司
没有发现记录