在网络微观尺度上提取超图中的高阶指纹方法

Higher-order motif analysis in hypergraphs

超图中的高阶序分析

https://www.nature.com/articles/s42005-022-00858-7

Code availability

The code for higher-order motif analysis is available at

https://github.com/FraLotito/higher-order-motifs.

摘要

大量的真实世界网络的新数据表明，系统单元之间的交互作用不限于成对关系，而常常涉及更多的节点。为了正确编码更高阶的交互作用，需要使用更丰富的数学框架，如超图，其中超边描述了任意数量节点之间的交互。在这里，我们系统地研究了高阶模式，它们被定义为顶点可能通过任何阶数的交互连接在一起的小型连通子图，并提出了一种有效的算法，从经验数据中提取完整的高阶模式配置文件。我们鉴定了具有不同高阶连接模式的局部尺度上的不同超图家族。我们还提出了一套度量标准来研究超边的嵌套结构，并提供了结构加强的证据，这是一种将更高阶交互作用的强度与在成对水平上交互更多的节点关联起来的机制。我们的工作突出了高阶模式的信息能力，提供了一种有原则的方法，在网络微观尺度上提取超图中的高阶指纹。

在过去的二十年中，网络已成为分析相互作用系统复杂拓扑的强大工具。从社交网络到大脑，几种系统被表示为节点和链接的集合，编码了单元对之间的二元交互。然而，越来越多的经验证据现在表明，许多这样的交互作用不仅限于对，而是发生在更大的群体中。例子包括合作网络、人与人之间的面对面互动、复杂生态系统中的物种互动、细胞网络以及结构和功能脑网络。

为了正确编码这样的高阶交互作用，需要使用更丰富的数学框架，如超图，其中超边描述了在任意数量的节点之间发生的交互。为了表征这些高阶系统，已经提出了代数拓扑的计算工具，以及包括中心性度量、有向性、聚类和同配性等常见网络概念的概括。明确处理高阶交互作用，包括它们的推断和重建，是必要的，以便理解网络形成机制、完全捕获高阶系统的真正社区结构，并提取它们在统计上验证的高阶骨干网。

考虑到高阶交互作用对于理解复杂系统的突现行为可能至关重要，因为它们已被发现对扩散、同步、社会和进化过程有深远影响。

网络系统可能因其在微观尺度上的连接模式而有所区别，这些模式编码了一个对系统功能通常相关的特性指纹。这可以通过测量网络模式来量化，网络模式是在观察到的网络中出现的小型连通子图，其频率远高于随机图零模型。对网络模式的分析揭示了“超家族”网络的出现，即显示类似局部结构的网络集群。这些集群倾向于将来自类似领域或通过类似进化过程演变的网络组合在一起。实际上，模式可以被解释为具有特定功能的元计算电路，可以被类似网络共享。例如，交通网络旨在简化交通流，而基因调控和神经元网络通常被认为是为了处理信息而进化的。这些系统中的功能差异反映在描述它们的网络中不同显著模式的出现。在这方面，研究模式也可以为网络类别的动态和弹性提供新的见解。

网络模式已在广泛的应用中使用。在生物学中，模式已广泛用于分析转录调控网络（即控制基因表达的网络）。研究表明，从细菌到人类的不同生物体表现出共同的调控模式，每种模式在决定基因表达方面都具有其独特的功能。同样，模式分析也被应用于展示复杂和灵活的神经功能是如何从大脑网络中的基本电路组合中产生的。此外，模式还被用作识别癌症的特征。最终，对越来越大的生物数据集的分析需求是开发更有效算法的强大动力。

除了生物学，模式也已应用于提供社交网络局部结构的指纹、早期检测金融网络中导致危机的结构变化，以及研究生态学中跨物种的直接和间接交互网络。

研究社区对提取现实世界系统网络微观尺度的指纹的兴趣导致了考虑更丰富的模式分析框架，包括扩展到更一般的网络模型，如有权重、时序和多层网络。有权重的网络可以根据其子图的链接权重的强度和一致性来表征。时序网络可以通过考虑时间限制的交互模式在拓扑和时间微观和宏观尺度上进行研究。统计上过度表达的小多层子图突显了如人脑这样的多层网络的局部结构。

然而，文献中提出的方法、算法和工具大多只考虑成对交互作用的模式，限制了我们表征涉及群体交互作用的系统的局部结构的能力。最近，Lee等人首次为填补这一空白做出了贡献：与专注于小节点集的交互模式的传统模式分析不同，他们研究了与连通超边相关的模式，特别是3个连通超边可能重叠的26种可能方式，允许提取有关超图设计原则的信息。

为了系统地研究高阶网络的局部结构，我们通过提供一种通用且可扩展的方法来调查高阶网络模式，这种方法自然地将Milo等人针对传统图提出的网络模式的概念和分析推广到超图。高阶网络模式被定义为在统计上过度表达的给定数量节点的连通子图，它们可以通过任意阶数的高阶交互作用连接。我们提出了这些新数学对象的组合表征，并开发了一种有效的算法来评估经验数据中每个高阶模式的统计显著性。我们展示了我们能够提取现实世界高阶系统的网络微观尺度的指纹，并突显了显示类似高阶局部结构的系统家族的出现。最后，我们提出了一套度量标准来研究超边的嵌套结构（即在超边的节点子集上定义的低阶超边的集合），并提供了结构加强现象的证据，即现实的群体交互作用如果得到丰富的成对交互作用嵌套结构的支持，它们会更强。

结果

模式分析已经成为网络科学中的一种基本工具，用于在微观尺度上提取网络的指纹，并识别它们的结构和功能构建块。通过直接扩展传统网络模式的定义，我们可以将高阶网络模式定义为在观察到的超图中出现的高阶交互作用的小连通模式，其频率远高于适当随机系统的频率。

与传统模式类似，执行高阶模式分析所需的步骤是：(i) 计算网络中每个高阶模式的频率，(ii) 将每个模式的频率与在零模型中观察到的频率进行比较，以及 (iii) 使用统计度量评估它们的过度或不足表达。用于计数传统模式的算法未能捕获关于群体交互作用的信息，因为它们没有考虑超边的模式。我们在方法部分报告了能够提取和评估高阶模式的算法和工具的详细提议。

阶数为3的基序

每个高阶基序在超图中的过度或不足表达（相对于空模型的丰度，见方法部分）被合并到一个显著性特征（SP，见方法部分）中，SP构成了网络局部结构的指纹。在本节中，我们使用阶数为3的高阶基序表征了经验网络在最小尺度上的局部连接性。

在计算了所有数据集的 SP 后，首先可以提出的问题是不同领域的超图在其平均 SP 上有何不同。我们通过将属于同一领域的所有网络的 SP 分组并取平均来计算领域的 SP（有关非聚合 SP 的更多信息可见补充说明4）。每个领域阶数为3的高阶基序分析突出了某些高阶交互模式的相对结构重要性（见图2a）。成对三角形 II 似乎在所有领域中都是高度过度表达的基序，而跨领域的最大差异出现在包含一个三重超边和至少一个成对边的基序中。在社会和技术领域，由一个三重超边和一个成对边三角形组成的基序 VI 被高度过度表达，表明在群体中交互的实体也倾向于单独交互。在合作作者网络中，最为过度表达的基序是 IV 和 V，这些基序涉及一个三重超边和一条或两条成对边，暗示这些领域中可能存在一种层级结构，导致并非所有节点都以成对方式平等交互，例如研究领袖与学生和博士后合作论文，而后者之间没有合作论文。在生物系统中也发现了类似的基序。此外，SP 还可以用于分析反基序，即高度不足表达的基序。在社会和技术领域，III 基序（没有任何成对交互的三重超边）是一个反基序，表明群体交互不太可能没有任何成对交互跟随或先行。生物和合作作者领域没有显示任何反基序。

另一个有趣的问题是领域分类是否可以自然地从所有经验超图的 SP 聚类中得出。我们通过考虑每个数据集中高阶基序出现分布之间的成对相关性作为距离（即其反值）进行层次聚类分析（见图2b）。分析显示出了两个主要聚类，即共享类似高阶交互模式的高阶网络家族。这里通过纯粹数据驱动的方式推断出的聚类再现了图2a 所显示的领域划分（社会和技术数据集在一个聚类中，生物和合作作者数据集在另一个聚类中），为数据集之间的相似性提供了更为细致的视角。

四阶基序在上一节中，我们系统地研究了最小的高阶基序。涉及4个节点的高阶交互模式的数量远远多于涉及3个节点的相应模式，从6个增加到了171个。尽管这种增长带来了分析上的困难，分析四阶高阶基序相比于三阶基序，能为网络的局部结构提供更细致的信息。

在图3a中，我们基于上一节的分析，将类似领域分组，显示其四阶高阶基序的显著性特征（SP）的平均值。沿着x轴的基序顺序最大化了不同簇之间SP的视觉差异。在x轴的左端，我们发现了一些在生物/合作领域中高度过度表达的基序，而这些基序在社会/技术领域中则表现不足。相反，在x轴的右端，我们发现了在社会/技术领域中过度表达的基序，而这些基序在其他领域中并不具有特征性。这一观察表明，x轴两端的基序携带了关于各簇结构差异的重要信息。

四阶高阶基序捕捉到的比三阶基序更丰富的结构信息在聚类分析中得到了突出表现（见图3b）。当我们聚焦于两个主要簇时，结果与之前的聚类分析相当。然而，自然出现了更丰富的簇内层次结构，以及两个簇之间更清晰的分离（见补充说明3）。

最后，我们通过它们最具代表性的、最过度表达的四阶高阶基序（见图3c）对社会/技术和生物/合作领域的簇进行了表征。社会/技术领域表现出更多涉及较低阶嵌套关系（例如，二元链接）的结构的过度表达，而生物/合作领域则倾向于较少但更高阶的关系。这一模式可能是由于在社会/技术领域中，人们在群体中交互时也可能会单独成对交互，因此群体交互通常由大量低阶交互支持。另一方面，人们往往在大群体中撰写论文，并且随着时间的推移，保持相同的研究群体，只有少量的成员增加或减少。因此，涉及仅有二元关系的模式在该领域中受到抑制。关于四阶基序中最过度和不足表达的基序的更深入描述，请参见补充说明5。

高阶交互的嵌套组织

我们现在将注意力转向表征大高阶超边的嵌套结构。我们定义大超边 h 的嵌套结构为其节点子集上存在的超边集合，并提取任意大小超边的嵌套结构统计信息。这种方法的优势在于它仍然提供了关于网络子模块局部结构的信息，而其计算复杂度仅在超图中的超边数量上是线性的。

首先，我们考虑不同大小的超边嵌套结构中平均边数的情况（见图4a）。网络按领域分组。生物和合著网络在超边大小增长时嵌套边数没有明显差异，而社会和技术网络显示出随着顺序达到5和6之后，增长趋势明显加速。

为了补充这一信息，我们还查看了随着超边大小增长，嵌套边的平均大小如何变化（见图4b）。在这种情况下，所有领域都显示出增长趋势，其中生物和合著网络的增长速度更快。因此，社会和技术网络往往在大超边的嵌套结构中有更多的边，但这些边的大小往往较小。相反，生物和合著网络表现出相反的行为。总的来说，这表明与我们之前的发现一致，在更高的规模上，社会/技术网络的基序也更系统地嵌套。

高阶基序与强化为了了解嵌套的二元交互的发生是否以及如何影响群体交互的强度，我们调查了每个超边的权重（即每次群体交互发生的次数）与嵌套的二元链接数量之间的相关性。我们发现了一个正向趋势，表明丰富的嵌套二元结构与超边权重之间存在相关性（见图5a）。我们称这种现象为“高阶结构强化”，类似于参考文献59中针对多层网络的发现。

此外，我们使用来自SocioPatterns的高中学生个人关系元数据，了解在个体之间存在友谊交互的情况下是否观察到了类似的强化行为。友谊数据通过两种方式收集，分别来自Facebook账户和问卷。在第一种情况下，两个学生总是互为朋友，而在第二种情况下，友谊可能是单向的。在图5b中，我们分析了Facebook和问卷中平均朋友数与接近超图中不同基序拓扑结构之间的关系。我们的结果表明，在三人超边中，学生之间的二元交互越多，组内的朋友数量就越多，进一步表明了存在强化机制。

网络基序框架被广泛认为是分析复杂网络的重要工具。网络基序能够突出网络的局部结构特征，并影响其动态，因此可视为网络的基本构建块，在生物学和社会网络分析等多个领域中有着广泛的应用。近年来，通过超图建模复杂系统已成为网络科学中的一个基本工具，这引发了在高阶交互的情况下如何识别和评估网络基序的问题。为了提取超图的局部特征，本工作引入了高阶网络基序的概念，这些基序是相对于空模型而言，统计上表现过度的小型、可能重叠的高阶交互模式。

我们提出了高阶网络基序的组合特征描述，并开发了一个高效算法，用于评估其在经验数据上的统计显著性。这些工具使我们能够通过聚焦于小型节点组之间的特征性高阶交互模式，提取各种现实系统的指纹，显示出具有相似局部结构的超图家族的涌现。此外，我们提出了一套研究超边嵌套结构的度量，并提供了结构强化机制的证据，即在二元交互较多的节点组中，高阶交互的权重更强。

类似于传统的二元网络基序，我们相信高阶网络基序可以为多个领域的应用开辟新的途径，特别是在众多现实世界系统中，随着对高阶交互重要性的认识不断增加。这一框架在数据密集型领域中的潜在应用，使我们提出的方法在可扩展性方面具有一定局限性。在本工作中，我们确实提出了一种算法，允许我们进行穷尽搜索，因此主要聚焦于规模为3和4的高阶网络基序。然而，我们相信还有空间开发其他方法，尽管牺牲了穷尽性，但可能使我们在更大规模的基序上获得深入见解。作为迈向这一方向的第一步，我们研究了更大规模的超边模式的嵌套结构。除此之外，我们认为针对高阶网络基序的统计评估开发抽样方法，将是更广泛现实应用的关键。

总而言之，我们的工作突出了高阶基序的信息力量，提供了一种初步方法，用于在网络微观尺度上提取超图中的高阶指纹。

方法

高阶基序分析涉及三个步骤：(i) 计算目标高阶基序在观测网络中的频率，(ii) 将其与空模型进行比较，(iii) 确定某些子超图模式的过度或不足表达。

在这里，我们提出了一种精确算法，用于计算超图中k阶高阶基序的频率。首先要有效解决的基本子任务是超图同构问题（即在重新标记下确定两个超图的等价性）。实际上，对于每一个具有k个节点的连通子超图的出现，我们需要更新相应k阶高阶基序的频率。通过枚举和索引所有k阶高阶基序及其所有重标记，这个问题可以有效地解决，从而允许通过哈希表在常数时间内更新和计算子超图模式的出现次数。由于我们仅对大小为3和4的模式感兴趣，这是可行的。实际上，涉及4个节点的高阶交互的可能非同构模式数为171，这一数量使得所有重标记可以存储在内存中。

为了枚举大小为k的子超图，我们使用了一种分层的算法。它首先迭代所有大小为k的超边，这些超边能够直接诱导基序，即一个大小为k的超边提供了构建k阶基序的所有节点。然后，它以迭代方式考虑较低阶的超边，直到它到达传统的二元链接。由于低于k阶的超边无法直接诱导基序，因此算法类似于参考文献83中的方式进行，并通过考虑子超图的邻域选择剩余的节点。

一旦选择了k个节点，为了有效地构建其诱导的子超图，我们迭代这些k个节点的幂集（对应于2^k个可能的超边），并仅保留在原始超图中存在的超边。

作为空模型，我们使用了Chodrow21提出的配置模型。我们从配置模型中采样n = 100次，并计算每个样本中的高阶基序频率。为了验证某些模式的过度或不足表达，我们使用了相对于随机网络提出的基序丰富度 Δi。

https://www.nature.com/articles/s42005-022-00858-7