论文标题：Hypergraph Computation

期刊：Engineering

DOI：https://doi.org/10.1016/j.eng.2024.04.017

微信链接：点击此处阅读微信文章

在现实世界的许多领域，大数据分析已成为研究和应用的主流趋势。然而，值得注意的是，在特定场景下仍存在有效数据不足、数据内部和数据之间关联复杂的挑战。这些挑战主要来自于数据采集与标注困难、隐私保护需求以及数据结构的固有复杂性。图结构是表示这种关联关系的典型工具，但它不能对系统中不同对象之间的高阶关联进行建模，因此难以充分捕捉对象之间的复杂关联。深入了解数据的内在特性，理解数据中包含的复杂关联，并采用新的计算范式来解决数据稀缺和关联复杂难题是至关重要的。

近日，清华大学高跃团队在中国工程院院刊《Engineering》发表题为“Hypergraph Computation”（超图计算）的综述性文章，介绍了三种类型的超图计算方法：超图结构建模、超图语义计算和高效超图计算，并进一步概述了超图计算在智慧医学和计算机视觉领域的广泛应用。该研究成果为复杂关联分析带来了新的进展。

超图计算的首要步骤是构建待研究对象的超图结构，在单模态数据内部、不同模态数据之间、以及来自不同来源数据之间挖掘其内在蕴含的高阶关联。前者通过基于网络和基于属性的方法对知识和规则中的高阶关联进行建模，而后者采用基于拓扑和特征距离的方法从数据中对高阶关联进行建模。通过上述方法构建的超边可以进一步高效地集成为一个统一的超图结构，以支持对象关系的全面建模并实现复杂高阶关联的精确表征。

在获得研究对象的高阶关联结构后，需进行超图语义计算以精确地表征节点语义。超图神经网络将超图的建模能力与神经网络的表示能力相结合，通过设计超图卷积算子实现结构化语义学习。基于谱域的超图神经网络通常包含两个步骤：首先，利用超图傅里叶变换将空间域信号映射到频谱域，并在该域中定义相应的卷积算子；其后，对频谱域信号进行卷积运算，再通过逆超图傅里叶变换将处理结果投回空间域。有别于基于谱域的方法，基于空域的方法是通过聚合相邻节点的表示来生成中心节点的新特征。

在实际应用中，基于结构的方法（如图方法和超图方法）往往面临大规模数据带来的高计算复杂度挑战。针对这一问题，超图高效计算主要关注面向大规模数据的高阶关联建模以及计算加速技术。高效的超图建模可以通过四种方式实现：超图分解、超图采样、分层超图建模和分布式超图建模。基于因式分解的超图建模方法通过两个子关联矩阵将顶点和超边之间的相关性编码为不同的低维潜在空间，尽可能地拟合初始的超图结构。基于采样的超图建模可以将原始的大尺度超图分解为多个较小的子超图，通过对每个目标顶点的多层邻居进行预采样来实现。在数据被分配分层标签的情况下，可以使用分层超图建模来处理大规模数据，将数据划分为多个子集，并使用 KNN(k-nearest neighbor) 等方法为每个子集构造一个子超图，通过融合局部高阶表示获得全局表示。分布式超图学习通过分布超图神经网络模型对数据进行优化，需要顶点的远程邻居之间的通信和同步，并通过聚合梯度来更新模型参数。

文章还系统总结了超图计算在智慧医疗和计算机视觉等领域的应用。以3D对象识别为例，实验结果表明，与传统基于数据的方法相比，超图计算在实现同等性能的同时可以减少80%的数据需求，或在相同数据条件下将任务性能提高52%。最后，文章介绍了基于PyTorch的开源深度学习库DHG(DeepHypergraph)，这是一个同时支持低阶和高阶关系建模的通用超图计算工具集。

文章信息：

Hypergraph Computation

超图计算

作者：

高跃*, 吉书仪, 韩向敏, 戴琼海

引用：

Yue Gao, Shuyi Ji, Xiangmin Han, Qionghai Dai. Hypergraph Computation. Engineering, 2024, 40(9): 188–201

开放获取论文：

https://doi.org/10.1016/j.eng.2024.04.017

更多内容

芯片电路设计新进展：布局优化精确算法助力成本降低

全新合成全通波导助力超快电子学发展

清华大学团队：智能光子，引领当下并重塑未来的颠覆性技术

李骏院士等：智能网联汽车安全

Engineering征稿启事：人工智能赋能工程科技