高阶交互建模的统计视角
A statistical perspective on higher-order interactions modeling
https://hal.science/hal-05571097v1/file/Hypergraph_review.pdf
摘要：
对高阶交互（HOI）进行建模已成为复杂系统分析中的一个关键挑战，因为许多现象不能仅通过成对关系来完全捕捉。超图通过允许两个以上实体之间的交互来泛化图，为表示这种复杂的依赖关系提供了一个强大的框架。采用统计和概率的视角对超图建模，我们提出了对这个新兴研究领域的引导式导览。
我们首先说明HOI在真实世界系统中的普遍性，在这些系统中，交互通常涉及实体组而不是孤立的对。然后我们介绍超图的基础概念和符号，讨论它们的描述性统计、基于图的表示，以及与它们的复杂性相关的挑战。我们进一步探索超图的各种统计模型，并解决节点聚类这一关键任务。最后，我们通过概述该领域中的一些开放性挑战来结束。
关键词：超图模型，节点聚类，
1 引言
对高阶交互（HOI）建模日益增长的兴趣源于这样一种认识：许多现象从根本上说比仅靠成对关系所能捕捉的要复杂得多。虽然网络及其作为图的数学表示捕捉了实体对之间的交互，但HOI本质上具有不同的性质，因为它们可能涉及两个以上元素的交互。考虑HOI提供了一种更丰富、更具表现力的方式来对各个不同领域的复杂交互进行建模，范围从社会网络分析（早期在Simmel 1902a,b中得到认可）或合著关系（Roy和Ravindran 2015），到生态系统（Muyinda等 2020）、神经科学（Chelaru等 2021）或化学（Restrepo 2026）等。
最近关于HOI的综述包括Battiston等（2020）；Bick等（2023）；Torres等（2021），它们主要关注来自物理学的复杂系统视角。我们选择关注HOI的统计建模和概率视角（Lee等 2025也采用了这一视角），并将主要关注超图。
本综述不涉及的内容。HOI分析是在数据收集步骤之后进行的，在该步骤中，HOI可以直接被观察到，或者从初步数据中推断出来（例如Lizotte等 2023）。这里不讨论这些HOI的构建或推断。单纯复形（Bianconi 2021）通常被作为超图的替代方案来建模HOI。它们带有拓扑空间中的节点位置，这一特征可能被证明是非常有用的。然而，有效的结构强加了一种嵌套性质，其中假设交互实体的每一个子集都在进行交互。虽然这种假设对于例如邻近交互（见下一节）可能是合适的，但在大多数应用中，这显得过于严格（合著例子是这种假设不合适的最突出的情况）。此外，即使在这种假设可能不是一个强约束的情况下，人们也可能会质疑将这种补充信息引入建模的适当性（例如，因为它可能会引入额外的噪声）。关于HOI的单纯性水平（即包含结构）的一个有趣探索可以在Landry等（2024）中找到。
为了使我们的贡献保持相对简洁，这里将不涵盖HOI上的动力学以及HOI的时间方面。最后，贝叶斯超图是概率模型，其中一组随机变量的依赖关系由HOI描述，从而泛化了贝叶斯网络（Javidian等 2020）。因此，该主题与我们在此关注的已观察到的HOI无关。
2 展现HOI的系统示例
借鉴Holme在其时间网络综述（Holme 2015）中的方法，我们首先对数据集类型，以及更广泛地说，对HOI自然发生的系统，进行一次快速的引导式导览。有趣的是，Holme引用的很大一部分系统在其原始格式中似乎是HOI，随后被简化为成对交互。我们没有提供出现HOI的数据集或出版物的详尽列表，而是强调这类数据的潜在普遍性。还要注意，任何二部网络都自然地产生一个HOI，或者换种说法，迄今为止许多HOI一直被视为二部网络。我们在3.2节讨论这两种方法之间的差异。
社会科学和动物行为学。社会交互是主要关注点，并推动了网络科学中绝大多数建模的发展。虽然二元交互是最简单的，但在社会学文献中早就认可了更大规模交互的作用和重要性（Simmel 1902a,b）。人类和动物（分别地）是社会交互中考虑的经典实体集。现在，这些交互中的大多数要么作为原始HOI进行采样，要么可以像成对交互那样从原始数据中自然构建。射频识别数据就是这种情况，其中记录了个体位置，并且交互发生在位于给定半径球体内的实体之间；以及在记录人类/动物聚集的野外观察中1。通信可能包括经典的电子邮件交换（具有多个接收者）或电话会议（在人类之间）以及非语言群体交互（Webb等 2023）。科学合作（例如合著）可能是HOI最突出的例子（例如Battiston等 2025；Roy和Ravindran 2015），也是解释HOI与所有成对交互的团之间差异的完美玩具示例。这些数据的变体包括在Web平台上发布的软件开发（Schueller等 2022）。更广泛的合作方法涉及这样的系统：当个人在同一家公司董事会共同任职时，他们会形成一个HOI（Aksoy等 2020）。同样，现在经典的“悲惨世界”数据集描述了维克多·雨果小说中的人物在书的不同场景中如何交互，已经从HOI的角度进行了研究（Aksoy等 2020）。对于出演电影的演员也可以这样做（例如，使用从互联网电影数据库中提取的数据）。
自然科学。
神经科学和连接组学是人类大脑内部HOI数据的重要来源，最近的方法依赖于功能磁共振成像数据（Santoro等 2024）或脑电图和脑磁图信号（Bilbao等 2026）。在考虑遗传疾病时也会出现HOI，其中基因突变与特定疾病有关（Aksoy等 2020），或者在交互实体是代谢物的代谢通路中（Cervellini等 2026）。更一般地，HOI在化学中用于描述参与化学反应的组分（Flamm等 2015）。生态学见证了针对HOI的关注度激增，其围绕的核心思想是大多数成对交互实际上是由额外的参与者介导的（Bimler和Mayfield 2023；Mayfield和Stouffer 2017）。
3 HOI的概念、符号和表示
我们首先在本节中给出围绕超图概念的基本定义，它将作为我们表示HOI的标准形式。随后，我们将继续讨论HOI的图表示，并强调其局限性。
3.1 超图
超图上的描述性统计。
引入的一些用于描述图的概念在超图中找到了直接的推广，而另一些概念，由于超图相对于图的复杂性增加，导致其定义具有更多的变异性。密度的情况就是如此。一个基本的定义将简单地计算超边的数量除以此类超边的最大数量，从而引入
在图统计文献中，传递性（transitivity）或聚类度量（clustering measures）的概念扮演着重要角色。这些本质上基于成对交互的概念，因为它们量化了“你朋友的朋友也是你的朋友”的倾向。这些概念在超图世界中没有自然的推广（尽管存在一些尝试性的定义，参见例如 Kim et al. 2023）。尽管如此，这些量也与“三角形”（即长度为3的环）的频率有关，并且转向更一般的模体（motif）频率概念，人们可以自然地将这些推广到超图背景下，唯一的限制是模体多样性的复杂性增加（Juul et al. 2024; Lotito et al. 2022）。
大规模超图特征。 尽管在21世纪初，大量文献探索了大规模真实图的特征，导致了诸如度数的无标度分布或小世界特性等一般规律的 formulization，但这种大规模探索迄今为止受到的关注很少。这可能是由于这些数据的计算复杂性，或者是结构的更大多样性阻碍了一般规则的出现。在中等规模上，我们要提到 Do et al. (2020); Lee et al. (2021) 探索了来自不同领域的十三个真实世界超图的特征，后一篇参考文献重点关注超边的重叠。
3.2 图表示
由于其复杂性，将超图简化为更简单的对象（如图）是很诱人的（参见图2作为说明），因为它们更容易处理。然而，这是以丢失信息或放松某些约束为代价的，正如我们现在解释的那样。
团图（Clique graph）。 超图的团图（也称为2-截面、团展开或团约简）具有相同的节点集，以及共享超边的节点之间的边。超图中的每条超边实际上在图中被约简为一个完全团。也可以使用加权版本，将关于超边大小的部分信息转移到投影图中。在任何情况下，这种朴素表示丢失了大量信息，并且不可能从团图重构超边。
线图（Line graph）。 超图的线图具有对应于该超图超边的顶点，以及重叠超边（即共享至少一个节点）之间的边。同样，这种表示丢失了信息（关于共享了多少以及哪些节点），并且不可能从其线图（唯一）恢复超图。线图主要用于总结超边之间的邻接关系（当两个超边共享一个节点时，它们是相邻的）。
二部图。超图的一种更精细的图表示形式在于考虑其二部表示（或星扩展图），其中超图的节点构成第一部分节点，而超边集构成第二部分节点。当原始节点在超图中属于某个原始超边（现在是第二部分的一个节点）时，就在二部图中从该原始节点画一条边指向该超边。在某些条件下，这是一个无损的过程。更准确地说，给定一个（简单）二部图并选择其中一部分作为原始节点集，人们可以在这个节点集上重构一个唯一的（多重集）超图，该超图最终可能包含多个超边和自环（见图3）。换句话说，二部图可以嵌入到超图的一般空间中，而简单超图可以投影到二部图中。
4 超图的统计模型
4.1 随机性在于超边：二部图模型的局限性
从上一节可以看出，使用二部图模型来推导超图模型似乎是自然的。然而，这可能会带来一些额外的代价，正如我们现在解释的那样。
随机图的配置模型包括从 n n 个节点上的所有可能图集合中进行均匀采样，同时遵守规定的度序列。对于超图，这些模型首先由 Ghoshal et al. (2009) 引入，重点关注三部（tripartite）和 3-均匀超图。后来，Chodrow (2020) 将此框架扩展到了非均匀情况。在这些工作中，节点度和超边大小都保持固定——这是依赖于超图二部表示的结果。配置模型对于采样那些匹配观测数据集的度序列（以及超边大小）的图（或超图）特别有价值，通常通过洗牌算法实现。因此，它经常作为统计分析中的零模型被采用。然而，从该模型中进行精确采样（相对于近似采样）提出了重大挑战，特别是对于超图（详见 Chodrow 2020 第 4 节）。
优先依附（PA）模型已在 Wang et al. (2010) 中提出，其中引入了超边增长和超边优先依附的思想。这些想法后来在 Guo et al. (2016) 中得到完善，最近又在 Jung et al. (2026) 中得到完善。Barthelemy (2022) 为顶点属于边的概率提出了一个非常通用的公式，因此归结为依赖于二部图表示。他的方法包括 Erdős-Rényi 类模型、配置模型、（某种）PA 模型以及随机几何模型。后一种模型旨在具有生成性，并且不容易适用于统计推断。
4.3 潜在空间和块模型
超图的潜在空间模型（LSM）提出了为超过 2 个潜在位置的子集构建邻近指标或度量的问题。Turnbull et al. 提出了一种随机几何超图模型，其中一旦某些半径的潜在位置球体相交，节点之间就会形成超边。为了避免强加单纯复形结构，半径随节点子集大小而异（随其增加），从而防止自动包含较小子集。这个确定性框架随后通过一个随机步骤进行了增强，尽管这引入了可识别性挑战，这些挑战通过在推断期间的先验分布得到缓解。Lyu et al. (2023) 提出了一种基于张量的 LSM，但仅限于 3-均匀超图。节点子集的邻近度量也可以依赖于其（相对）潜在位置的平均值（例如算术平均、几何平均、Hölder 平均等）。这是 Fritz et al. (2026) 追求的途径，并结合了潜在双曲空间，利用更具表现力的几何结构来处理分层和嵌入结构。该工作还包含了一个用于超图统计分析的最有前途的工具：样本到总体（sample-to-population）估计过程，包括用近似值替换模型似然，其中仅对未发生的交互进行采样，而发生的交互（即超边）全部包含在内。
块模型将在第 5 节讨论，因为它们的离散潜在空间直接与节点聚类相关。我们在此提到 Ng and Murphy (2022) 的工作，该工作提出了超边上的混合模型，因此与节点聚类无关。最后，Balasubramanian (2021) 提出了一种非参数超图元（hypergraphon）模型，但仅限于均匀情况。
5 超图上的节点聚类
我们在寻找什么样的聚类类型？
最简单的聚类类型是社区（community），在图的背景下，其特征是内部连接紧密但外部连接较弱的节点组。出现的第一个问题是：超图中的社区是什么？人们可以认为超边构成了（重叠的）社区，在这种情况下聚类是直接观察到的。一个更精细的定义会指出，经常共享相同超边的节点形成一个社区。这里的一个关键挑战是是否应该考虑这些超边的大小？例如，在图1的玩具超图中是否存在社区结构？在那里，节点组{1,2,3,4}和{5,6,7}具有同样多的内部和外部超边（分别为一个），但内部超边的大小更大。事实上，可能存在各种各样的定义，这在文献中产生了同样多样化的提议。
我们能希望检测到它们吗？节点聚类问题与信息论极限的存在密切相关，这些极限阻碍了恢复或检测这些聚类。这个问题最初是在均匀超图的背景下进行探讨的，从而限制了结果的范围。事实上，尽管超图可以被视为不同 s s值的 s s-均匀超图的集合，但并非所有层都包含恢复潜在底层结构所需的信息。稀疏超图中的非均匀结果包括 Zhen 和 Wang (2023)，其中包含模型参数和社区的收敛界，以及 Dumitriu 等 (2025)，当模型参数已知时，该研究提供了关于社区的弱一致性结果。最近，Ruggeri 等 (2024) 建立了在非均匀超图中有效的首个检测结果，然而这仅限于超边的概率表示为成对概率之和的特定设置。这种二元限制使得该模型更类似于图的设置。
基于模型的方法 - SBM 除了社区之外，块模型方法简单地将聚类定义为具有相同（条件）交互概率的节点组。过去几年文献中出现了许多提议，以及度校正的变体（Ghoshdastidar 和 Dukkipati 2014；Chodrow 等 2021；Yuan 等 2022；Brusa 和 Matias 2024）。
其他方法。 超图中节点聚类的其他方法包括基于模块度（modularity）的方法。模块度定义严重依赖于社区的定义，并且在该领域已经遵循了各种方向。读者将在 Poda 和 Matias (2024) 中找到这些方法的比较。谱聚类提供了一种替代方案。大多数现有方法严重依赖于（加权）团图表示（Ghoshdastidar 和 Dukkipati 2017），代价是丢失信息，而其他方法要么局限于单纯结构，要么局限于均匀超图（del Genio 2025）。最后，已经提出了一些基于随机游走的方法（Swan 和 Zhan 2021）。
6 结论与下一步挑战
可扩展性肯定是超图建模中最具挑战性的问题之一。它体现在两个方面：一方面需要能够处理潜在巨大的超边大小，另一方面更普遍地需要处理大型系统（即个体和交互的数量庞大）。近似推断无疑是朝着这个方向发展的一个有前途的途径，例如Fritz等人（2026）所开创的那样。需要开发用于统计分析的高效软件，以与现有的库如HyperNetX（Praggastis等人，2024）相匹配。在非均匀超图中获得社区检测的不可能结果或相变阈值似乎很困难，这无疑是该领域接下来的挑战之一。正如前面所强调的，均匀超图的结果在这方面不会有帮助，因为并非所有层都需要提供信息。此外，唯一可用的阈值（Ruggeri等人，2024）严重依赖于二元类型的建模假设。迫切需要用于超图中社区检测的合成基准数据。这些数据可能不应依赖于超图随机块模型（SBM），以免在与其他方法的比较中使基于模型的方法占据优势。已经提出了一些不够令人信服的方案（参见Poda和Matias 2024中的讨论），这再次引发了在超图背景下如何定义社区这一棘手的问题。
原文链接：https://hal.science/hal-05571097v1/file/Hypergraph_review.pdf
热门跟贴