Exact and sampling methods for mining higher-order motifs in large hypergraphs 2023

在大型超图中挖掘高阶主题的精确和采样方法

https://link.springer.com/article/10.1007/s00607-023-01230-5

Lotito, Q.F.: Higher-order motif discovery sampling algorithm (2022).

https://github.com/FraLotito/sampling-motifs

摘要

网络模体是在系统中频繁观察到的重复出现的小型交互模式。它们揭示了不同领域复杂网络的拓扑结构与动态之间的相互作用。在这项工作中，我们专注于在非常大的超图中计算小型子超图模式的出现次数的问题，其中高阶交互连接任意数量的系统单元。我们展示了如何直接利用高阶结构与传统的确切模体发现数据挖掘技术相比加快了计数过程。此外，通过超边采样，以小幅估计模体频率的误差为代价，进一步提高了性能。我们在描述面对面互动、合著关系和人类通信的几个真实世界数据集上评估了我们的方法。我们展示了我们的近似算法允许我们更快地提取高阶模体，并在更大的规模上进行，超出了精确方法的计算限制。

关键词：网络模体，超图算法，高阶网络，复杂网络

1 引言

网络模体是出现在观察到的网络中的具有显著频率的一小组节点之间交互的重复模式。模体分析已经成为研究网络微观结构的重要工具，突出了现实世界网络系统拓扑结构和动态之间的相互依赖性[1, 2]。事实上，具有紧密功能相互作用的系统倾向于显示出类似的过度和不足表示的交互模式[3]。

网络模体在许多不同领域找到了广泛的应用，如生物学[4-6]、神经科学[7]、医学[8]、社交网络分析[9]、金融[10]和生态学[11, 12]。

鉴于它们在现实世界中的多种应用，网络模体的概念已经被扩展到各种更丰富、更灵活的网络模型，包括加权[13]、时间[14, 15]和多层[16, 17]网络。最近，越来越多的兴趣投入到了利用更复杂的数学工具，如超图[22]，对现实世界系统进行建模，其中超边编码了任意数量单元之间的关系，包括合著[20]和面对面[21]交互。在超图中，可以识别高阶模体，即通过超边不仅通过成对边而且通过编码三个或更多节点之间关联的超边进行交互的节点集合。特别是，高阶模体可以定义为固定大小超边的重叠模式[23]，或者更传统地，通过研究给定节点数的所有可能的连接子超图模式[24]。

独立于底层网络模型，所有模体分析算法都涉及以下步骤：(i) 计算观察到的网络中每个模体的出现次数，(ii) 计算观察到的网络的适当随机化中每个模体的出现次数，以及(iii) 评估每个模体的过度和不足表达。在目标大型网络中计算每个模体频率的问题在计算上具有固有的挑战性，因为它等同于子图同构问题，这是一个众所周知的NP完全问题。此外，对于模体频率的统计评估，计数步骤在随机图模型的每个样本上重复。因此，模体分析的精确算法往往随着图和模式大小的增加而扩展得非常差。一个常见的算法设计模式是依靠近似算法来加快计算速度，尽管牺牲了解决方案的质量。特别是，抽样方法是模体发现任务的流行选择。

大规模现实世界数据集的日益可用性，这些数据集包含群体交互，呼吁开发更高效、更可用的高阶模体发现算法。在这项工作中，我们基于我们关于计算涉及给定数量节点的所有可能高阶交互模式的初步结果[24]，并提出：

• 一个高效的精确算法，用于执行涉及3个和4个节点的高阶模体分析，包括高效解决小实例的超图同构问题和构建顶点诱导的子超图；

• 一种基于超边抽样的近似方法，它克服了精确算法的可扩展性问题，仅以非常有限的准确性下降为代价；

• 将近似方法应用于研究几个感兴趣网络中的5阶高阶模体（通常对精确算法来说难以处理）。

本文的组织如下。第2节我们调查相关工作。第3节我们介绍基本定义并形式化感兴趣的问题。第4节我们概述了解决超图中高阶模体发现问题的精确问题的提议。第5节我们为同一问题提出了一个抽样算法。第6节我们评估了我们的提议。第7节我们总结了本文。

2 相关工作

网络模体已经在以下领域得到了广泛研究：

• 在网络科学领域，因为它们在研究局部结构和复杂网络的拓扑结构与动态之间的相互作用方面的重要性；

• 在数据挖掘领域，由于从大型图中枚举一定大小的连通子图问题的复杂性。

在本节中，我们提出对这两个领域相关先前工作的简要调查，并突出我们对这两个领域的贡献。

2.1 网络科学

网络模体通过微观尺度上的偏好交互模式描述复杂网络。它们可以被解释为在系统功能中起作用的基本电路[1, 2]，因此能够区分代表不同领域或具有不同功能系统的网络[3]。网络模体的概念已经被扩展到各种更通用的网络模型中，以编码和量化具有更丰富特征集的交互模式。Onnela等人将网络模体推广到加权网络，根据它们的强度和一致性来表征子图[13]。在时间网络中，拓扑和时间微观尺度被描述为在限制时间窗口内的交互模式[14, 15]。Battiston等人将模体分析扩展到多层网络，通过考虑跨越多个层的过度表达子图[16]。最近，模体分析甚至被扩展到考虑更高阶交互模式，即涉及超图的微观尺度上的交互模式，以固定大小的连接超边模式[23]。然而，它们没有遵循Milo等人首次提出的传统网络模体方法[1]。

2.2 数据挖掘

由于模体发现任务具有实际效用但计算成本高昂（相当于已知的NP完全问题的子图同构问题），围绕这个问题已经发展了大量的文献。特别是，开发更快的模体分析算法的历史主要是由需要分析的生物数据集不断增长的规模驱动的。模体发现算法可以分为两大类：精确计数和抽样方法。每种类型的算法都有优点和缺点：精确算法允许提取每个模体的正确出现次数；然而，它们通常速度慢且内存密集。抽样方法通常更快，但它们需要被设计为避免偏见，并且只提供每个模体计数的近似值。历史上，社区的兴趣已经从开发精确计数算法转移到开发能够处理更大网络并以可接受的时间提取更大模体的近似算法和启发式算法，尽管牺牲了准确性。最初的模体发现算法是Milo等人提出的穷举枚举方法[1]。给定数量节点的所有可能子图模式的枚举计算成本高昂，只能真正分析大小为3和4的非常小的子图。之后，提出了大量改进。其中，我们突出了ESU和RAND-ESU算法[25]。ESU是一种高效算法，它利用树状数据结构从大型图中枚举给定大小的所有诱导子图。RAND-ESU是一种无偏抽样方法，建立在ESU之上，通过抽样树的分支进行访问。有关这些算法的更深入概述，感兴趣的读者可以参阅[26]。

虽然经典网络模体的研究量巨大，但广义网络模体的数据挖掘文献远未如此完整，时间网络[27, 28]有一些例外。特别是，与超图模体发现相关的计算方面在很大程度上被忽视了。在他们的开创性论文[29]中，Horváth等人提出了一个增量多项式时间算法，用于挖掘超图数据库中频繁子超图的相关问题。在他们的设置中，子超图的频率对应于数据库中包含查询子超图的超图数量。在只考虑一个输入超图的模体挖掘情况下，这个算法只能发现输入超图中是否存在某种子超图模式。因此，Horváth等人提出的算法不适用于超图的模体挖掘，因为我们想要计算给定输入超图中每种可能的子超图模式的确切出现次数。Preti等人解决了在单纯复形中挖掘频繁模式的问题[30]。尽管超图和单纯复形都可以表示更高阶的交互，但这两个数学对象呈现出一个重要差异：单纯复形尊重向下封闭属性（即在超图的情况下，如果超边e存在于超图H中，那么e的所有真子集也存在于H中）。Lee等人提出了一套算法，包括一个精确的、并行的和一个近似的算法，用于在超图中挖掘模体[23, 31]。然而，他们只关注提取固定大小超边重叠模式的问题。

2.3 贡献

在我们之前的工作[24]中，我们采用了传统方法，并将Milo等人[1]提出的原始网络模体定义扩展到超图，研究了给定数量节点之间所有可能的成对和群体交互模式。在[24]中，我们提取了现实世界超图的微观尺度特征，并识别了与属于不同领域的超图家族相关的关键模体。在这里，我们在第一项工作的基础上进一步发展了我们的算法，用于高效计算小规模子超图模式的频率。虽然我们的提议可以在每个数据集中超越基线，但精确方法由于计算成本高，无法扩展到大型超图或超过四个节点的模式。

因此，本文介绍了一种基于超边抽样的高阶模体提取的近似方法。我们展示了我们的抽样方法在估计模体频率时仅以最小的误差为代价，显著加快了计算速度，并允许我们分析超出精确方法计算限制的更大高阶模体。

3 预备知识和问题陈述

在这里，我们回顾一些基本定义，并对我们感兴趣的问题给出正式描述。

现在我们可以更正式地定义与同构问题相关的概念，这是网络模体发现的基础理论工具。

正如之前提到的，要对一个系统进行高阶模体分析，需要 (i) 计算超图中每个查询高阶模体的频率，(ii) 将每个查询高阶模体的频率与在零模型中观察到的频率进行比较，以及 (iii) 评估每个查询高阶模体的过度或不足表达。在这项工作中，我们主要关注第一步，即模体发现，因此我们将使用高阶模体来指代涉及一定数量节点的所有可能的子超图模式。在图1中，我们列举了所有3阶的高阶模体。

4 挖掘高阶模体

显然，枚举给定大小的连接子超图的所有模式是模体分析中最昂贵的子任务。考虑到这一步还必须在随机化网络中重复进行，这一步骤的权重就更加有影响力了。为了精确解决这个问题，在本节中，我们提出了一个基于将超图投影到图上并在上面使用最先进的模体分析算法的基线算法。此外，我们提出了一种更有效的方法，直接利用高阶结构来构建指定大小的子超图。

4.1 基线算法

虽然传统算法无法识别多元交互的模式，但它们可以作为更复杂算法的例程。在我们的基线中，我们考虑了超图的投影图。

通过运行一个经典算法（例如，ESU [25]），我们可以高效地枚举投影图中大小为k的连通子图。然而，这些子图只是候选的高阶模式，有两个潜在的原因：（i）它们不包括高阶交互；（ii）即使大小为k的子图s在投影图中是连通的，由s中的顶点和超边E诱导的子超图可能不是连通的。我们在图2中突出了这些陷阱。

为了解决这些问题，我们构建了由候选模式的k个节点诱导的子超图（见第4.3节），并检查这个子超图是否连通。如果是，那么可以简单地更新频率哈希映射，否则，输出将被丢弃。这种方法的更正式解释在算法1中有报告。总的来说，基线继承了ESU [25]的复杂性，加上计算超图的团投影的预处理成本。

4.2 高效算法

在前面的算法中，最昂贵的步骤显然是ESU子程序。此外，性能受到超图投影可能非常密集，以及许多子图因不满足诱导子超图连通性的要求而被丢弃的事实的广泛影响。为了解决这些问题，我们直接在超图上工作，设计了一个高效的算法，该算法利用了现实世界系统中高阶结构的包含性质。我们分别优化了3节点和4节点模式的两种情况。

3节点模式

如图1所示，涉及三个节点的两种模式仅由成对关系组成，而其他的则涉及一个3阶超边。要发现后者，只需遍历所有3阶超边，然后恢复嵌套的成对链接以构建模式（“填充”超边，见第4.3节）；由于其节点是同一个超边的一部分，子超图显然是连通的。然后，我们可以忽略所有更高阶的交互，只关注成对链接，因为我们感兴趣的是计算图1中前两种模式的频率。在这种情况下，我们可以依赖ESU。然而，这一次，它将需要处理少得多的边。每次ESU返回一个输出时，节点的三元组可能已经在前一步中被计数过了（即，成对模式和3阶超链接之间的重叠）：在这种情况下，该三元组被丢弃。第一步的复杂性与3阶超边的数量成线性关系，而第二步继承了ESU算法的复杂性。关于3阶高阶模式的算法的正式描述在算法2中有报告。

4节点模式

4阶模式的算法与3阶模式的算法类似，尽管需要考虑更多的细节。人们仍然可以遍历所有4阶超边，通过考虑丰富的嵌套结构来计数模式（可以观察到这一次3阶超边也可以嵌套），并丢弃所有的4阶超边。然而，作为第二步，还需要遍历所有的3阶超边，并考虑所有可能的邻居；事实上，3阶超边只定义了一个具有3个节点的子超图，而我们要求的是4个节点。邻居可以通过考虑只添加1个新节点的所有边来列出，因为已经固定了3个节点。最后一步是只考虑成对交互，我们再次依赖ESU。在这里，第一步的复杂性与4阶超边的数量成线性关系，第二步的复杂性与超边的总数成二次方（在线性地遍历3阶超边的数量，然后对于每个超边线性地探索其邻居），最后一步继承了ESU算法的复杂性。关于4阶高阶模式的算法的正式描述在算法3中有报告。

4.3 算法细节

计算高阶模式可以被解释为枚举所有可能的大小为k的连通子超图，并将它们分配给一个同构类。对于小值的k，将一个连通子超图分配给一个同构类的有效方法是依赖于哈希映射。可以生成并哈希每个可能的涉及k个节点的高阶交互模式，以及所有可能的重新标记。重新标记很重要，因为相同的子超图可以用不同的顶点标签存储。例如，我们有6种不同的涉及3个节点的高阶交互模式，每种都有3!种可能的重新标记；最终，哈希映射将包含6 · 3! = 36个条目。可以将哈希映射用作计数器，因为每个观察到的子超图都是一个键。在枚举了所有子超图之后，每个模式的最终计数就是属于同一同构类的哈希映射中所有条目的总和。我们在图3中展示了这个过程的总结。考虑到所涉及的子超图的大小，我们可以假设这个过程产生一个恒定的时间成本。

我们的算法中的另一个重要例程是构建顶点诱导的子超图。给定一组顶点V'，我们感兴趣的是查询所有超边的集合，以提取那些所有端点都在V'中的超边。这就是我们在前几节中提到的“填充”一组顶点。对于我们的特定情况，这个问题可以再次依赖哈希映射来有效解决。我们可以哈希超图中的每个超边：这确保了我们能够在恒定时间内检查超边的存在。由于我们只对解决大小为3或4的查询顶点集合感兴趣，我们可以轻松地生成所有可能的或个子集（我们也可以忽略空集和单元素集），并在恒定时间内检查每个子集是否是现有的超边。我们在图3中展示了这个过程的总结。总的来说，鉴于我们对非常小的顶点集合感兴趣，我们可以在恒定时间内构建顶点诱导的子超图。

5 用于计数高阶模式的抽样方法

可扩展性是精确模式发现算法的一个持续问题。模式分析有许多现实世界的应用，需要处理庞大的数据集。然而，对于现实的输入和模式大小，精确的模式发现算法很快就变得不可行。为了解决这种复杂性，我们提出了一种基于超边抽样的近似方法。

算法4通过替换抽样S次超边e，并枚举所有包含e的给定数量节点的连通子超图。样本数量S控制了近似结果的质量。然而，直接从超图中抽样超边会导致不可靠的结果。超边大小的分布是不均匀的，这使得算法经常抽样大小为2的超边，而很少抽样大小为4的超边。这扭曲了特定子超图模式的估计。为了缓解这个问题，我们采用分层抽样，将抽样过程分割，以保证不同大小的超边得到平衡的考虑。设Sk为分配给大小为k的超边的样本数量，使得S = Σk Sk。我们通过经验估计每个k的适当Sk值，通过穷举搜索不同的值组合，并选择最大化定义的质量函数的那些（见第A节）。

抽样算法的执行方式与精确方法类似（因此我们避免在伪代码中明确重复一些细节）。如果我们的目标是发现大小为k的模式，那么对于所有抽样得到的尺寸为k的超边，我们拥有构建目标子超图所需的所有顶点。不需要进一步探索邻域来添加新节点到模式中。这一步的复杂性与样本数量Sk成线性关系。

然后，对于所有抽样得到的尺寸小于k的超边，需要对可能的不同级别的邻域进行一些探索。这些步骤的复杂性每个都是样本数量Sk的线性乘以探索每个级别的线性因子，即超边的数量。此外，对于每个模式，重复之前提到的“填充”超边的过程，以构建顶点诱导的子超图并计数正确的模式实例。同样，这些例程需要恒定的时间。

为了估计每个模式的确切计数，算法将观察到的计数乘以伪代码中报告的抽样某个特定模式的概率所给出的校正因子。为了简化校正因子的计算，算法丢弃在探索超边e的邻域过程中遇到的所有子超图，这些子超图至少包含一个比e具有更高基数的超边。换句话说，只有当采样到最大基数的超边时，才考虑子超图的模式。鉴于这种方法，很容易证明估计器是无偏的。

6 实验评估

为了评估在进行高阶模式发现时算法性能的改进，我们收集了代表具有群体交互的现实世界系统的多种超图数据集。这些改进包括：（i）利用高阶结构而不是在超图投影上应用经典方法，以及（ii）近似模式频率。除了评估性能外，我们还研究了抽样算法的准确性，并利用抽样方法研究了5阶高阶模式。所有实验都在一台配备8核（2.2GHz）Intel Xeon CPU和94GB RAM的机器上进行，运行Ubuntu 20.04.4 LTS。本文介绍的算法是用Python3实现的。代码是公开可用的[32]。此外，本文介绍的所有算法都包含在用于高阶网络分析的Python库Hypergraphx中[33]。

6.1 数据集

我们从不同领域收集了多种现实世界的数据集，描述了面对面交互、合著关系和电子邮件通信。

合著数据（dblp、历史和地质学）[34]自然编码为一组节点（作者）参与高阶交互（科学论文）。同样，电子邮件数据（EU）[34]自然编码为一组高阶交互，因为电子邮件可以同时有多个收件人。然而，需要从面对面交互的数据（小学和高中）[34]中推断高阶交互。在这种情况下，如果相应的成对相遇同时发生，则将大小为k的团簇提升为k阶群体交互。数据集的汇总统计数据在表1中报告。数据集以及预处理脚本是公开可用的[32]。

6.2 性能评估

在表2中，我们比较了我们的精确算法与基线算法在执行运行时间方面的高阶模式发现。

我们展示了直接利用高阶结构可以加速计算。高效的算法在每个数据集上都优于基线算法。

此外，值得一提的是，使用基线算法对dblp的4阶模式进行分析在合理的时间内是不可行的。在合著数据中观察到更大的增益。合著系统被证明显示了由少数大平均大小的超边组成的超边嵌套结构[24]。事实上，这些类型的系统是我们算法的理想场景。我们可以注意到，在社交数据集中增益不是很明显，这些数据集往往受到低阶交互的密集模式的支配[24]。

在表3中，我们展示了在不同数据集上使用多个S值（即控制样本数量的参数）的抽样算法的执行运行时间（以秒为单位）。合著和社交数据集的不同规模需要不同的样本大小才能获得可比质量的结果。由于3阶模式的分析已经很容易完成，我们只考虑4阶模式发现的任务。我们展示了超边抽样显著提高了性能。正如预期的那样，参数S严重影响了运行时间。与往常一样，结果的准确性（S值越高，估计越准确）和执行运行时间之间存在权衡。

6.3 抽样方法的准确性

除了评估抽样方法的运行时间外，评估估计输出质量与精确高阶模式配置文件的比较也很重要。我们计算模式配置文件[24]，将观察到的模式频率与零模型[35]上的频率进行比较，以评估它们的统计显著性（我们从配置模型中采样N = 10次）。

我们从以下方面评估估计的模式配置文件的质量：

- 估计值和精确高阶模式配置文件之间的皮尔逊相关系数ρ。该系数将接近1的值分配给高度一致的配置文件，将接近-1的值分配给高度不一致的配置文件。

- 估计高阶模式配置文件的最大绝对误差（MaxAE）。

- 估计高阶模式配置文件的平均绝对误差（MAE）。

在表3中，我们展示了即使在与超图的总大小相比样本数量很少的情况下，我们也获得了良好的结果。随着S的增加，输出质量的度量有所提高。在输出质量、S和执行运行时间之间找到一个好的折中对于现实世界的应用将是至关重要的。输出质量的度量是在每个S值的10次重复中平均得出的。

另一种评估指标是不同现实世界超图的模式显著性配置文件[1, 24]的相关矩阵。在图4中，相关矩阵显示了两个“超家族”现实世界超图的出现，这与[24]中的方式类似。聚类倾向于将社交数据和合著数据分开。这进一步证明抽样方法仍然能够捕捉和突出显示可能与网络功能相关的高阶交互模式。

6.4 应用：挖掘更大的高阶模式

近似方法不仅加快了大型数据集的模式分析速度，还允许研究更大的交互模式。精确计数算法仅适用于提取3阶和4阶模式。在这里，我们采用我们提出的抽样算法，以5阶高阶模式为特征，对两个现实世界的超图进行描述，即历史和高中。为了评估结果的统计显著性，我们将结果与配置模型的结果进行比较。我们使用[24]中提出的相同的统计评估方法，即考虑每个模式相对于配置模型的相对丰度[35]。在图5中，我们展示了这两个现实世界超图中过度表达最多的5阶高阶模式。我们可以注意到，即使在这个规模上，我们仍然观察到合著数据（平均大小的大交互数量少）和面对面数据（平均大小的小交互数量多）的特征模式。这与[24]中提出的现实世界超边嵌套结构的结果一致。

7 结论

在本文中，我们提出了一个用于在超图上发现高阶模式的第一个算法框架，如[24]中定义的。我们为3阶和4阶高阶模式的分析开发了一个高效的精确算法。这种精确算法利用超边及其嵌套结构来高效地枚举给定大小的子超图。我们证明了直接考虑数据的超图结构比在投影数据上工作的网络模式的传统计算框架有更好的性能。我们开发了一种基于超边抽样的近似方法来克服精确算法的可扩展性问题。我们证明了这种近似算法在运行时间上带来了巨大的收益，而对结果的准确性影响很小。此外，我们的抽样算法允许分析更大的模式，这些模式在精确方法中在计算上是不可行的。我们相信，像我们提出的抽样算法这样的更快的高阶模式分析算法，可以为激动人心的应用铺平道路。在这个方向上，未来工作的重要方面是开发具有强大近似保证的抽样算法，以及研究针对不同类别的高阶交互模式的更有效的抽样策略。

附录 A 参数搜索 

我们近似算法需要不同的参数。参数 S 控制采样超边的数量，用以估计子超图模式的数量。如果设计不当，直接从超图中采样超边会导致不可靠的结果。实际上，在真实世界的超图中，超边的大小分布并不均匀，导致算法经常采样大小为 2 的超边，而较少采样大小为 4 的超边。这会导致对涉及 3 或 4 个节点的高阶模式的估计较差。为了解决这个问题，我们对采样过程进行分层，将特定的采样预算分配给不同大小的超边。这确保了所有大小的超边都有均衡的表示。设 Sk 为分配给大小为 k 的超边的采样数量。我们将所有 k 的 Sk 之和固定为 S。我们通过穷举搜索不同的值组合来估算 Sk 的经验最佳值，并选择那些使质量函数（精确高阶模式分布与估计值之间的皮尔逊相关系数 ρ）最大化的值。我们在两个数据集上进行了分析，分别属于两个宏观领域：高中和历史。我们考虑阶数为 4 的模式，因此我们需要估计 S2、S3 和 S4，分别代表从阶数为 2、3 和 4 的超边中采样的数量。鉴于 S2 + S3 + S4 = S，可以固定 S2，并将 S3 和 S4 参数化为 S2 的倍数，然后进行穷举搜索。我们在图 A1 中展示了结果。通过平均两个矩阵的结果，我们得到质量测度在 S3 = 3S2 和 S4 = 2S2 时达到最大值。我们在实验中使用了这些参数。

https://link.springer.com/article/10.1007/s00607-023-01230-5