A Survey on Hypergraph Mining: Patterns, Tools, andGenerators
超图挖掘综述:模式、工具和生成器
https://arxiv.org/pdf/2401.08878
摘要
超图是模拟现实世界中群体互动的自然而强大的选择，通常被称为高阶网络。例如，在模拟合作网络时，合作可能涉及的不仅仅是两个人，而是三个人或更多人，使用超图可以让我们超越成对（二元）模式，捕捉群体（多元）模式。超图的数学复杂性为超图上的学习和挖掘提供了机遇和挑战，超图挖掘通过超图建模增强了我们对底层系统的理解，研究中的关注度日益增加。研究人员在现实世界的超图中发现了各种结构模式，促进了挖掘工具的发展。此外，他们设计了生成器，目的是再现并因此揭示这些模式。在这篇综述中，我们提供了当前超图挖掘领域的全面概述，涵盖了模式、工具和生成器。我们为它们提供了全面的分类，并进行了深入讨论，以提供对未来超图挖掘研究的见解。
CCS概念：• 计算数学 → 超图；随机图；图算法；
• 计算理论 → 图算法分析；• 信息系统 → 数据挖掘；•
以人为中心的计算 → 社交网络分析。
其他关键词和短语：超图挖掘，超图生成器，高阶网络
1 引言
群体互动在复杂的现实世界系统中普遍存在，并出现在各种情境中，包括研究合作[16]、蛋白质相互作用[50]和商品共同购买[140]，仅举几例。这些涉及多个个体或实体的高阶互动可以自然而有效地建模为超图[15, 130]。
超图是对（成对）图的概括，由节点和超边组成。超边定义为节点的非空子集，自然地模拟涉及任意数量节点的互动。与图中只能连接两个节点的边不同，每个超边可以连接任意数量的节点。超边大小的灵活性为超图提供了强大的表达能力，使它们能够准确模拟图所不足的广泛群体互动。例如，在图1中，共同作者关系被建模为超图，其中每个节点代表一个研究者，每个超边代表涉及其组成节点所代表的研究者的共同作者关系。需要注意的是，共同作者关系不适合用图中的边来表示。当三位研究者合作撰写一篇论文时，连接所有可能的研究者对无法区分群体互动与由不同对研究者共同撰写的三篇论文。
超图的这种固有表达能力导致了它们在包括但不限于推荐系统[138]、计算机视觉[89]、自然语言处理[41]、社交网络分析[8]、财务分析[142]、生物信息学[50]和电路设计[57]等多个领域的应用。
受到使用（成对）图模型理解现实世界系统的成功启发，最近的研究深入理解了模拟这些系统的现实世界超图的结构。特别是超图建模的灵活性，即每个超边的大小，引入了在图的背景下未曾考虑过的独特视角。因此，开发了专门的工具来分析超图的独特结构特征。利用这些工具，揭示了现实世界超图中的多种非平凡的局部结构模式[16, 83, 94]和全局结构模式[43, 77]。这些模式中的大多数明显区分了现实世界超图和随机超图，通常伴随着直观的解释或背后的机制。它们显著增强了我们对现实世界系统的理解。
验证我们对结构属性理解的一种方法是使用超图生成器（或超图生成模型）。本质上，如果我们能够将我们的理解实现到能够再现特定观察到的模式的生成器中，那么我们的理解就成为了对所观察到的现象的合理潜在解释。因此，结合超图结构模式的普遍性，超图生成器在最近的研究中吸引了越来越多的关注[17, 43, 54, 81]。这些生成器成功地产生了合成超图，再现了在现实世界超图中观察到的特定模式，从而为理解和预测超图的结构提供了宝贵的见解。这些合成超图也对模拟和评估超图算法非常有价值，特别是在收集或跟踪现实世界超图不切实际的情况下。此外，这些生成器可以用来创建匿名数据集（特别是结构上接近给定数据集的合成数据集），正如在图数据上广泛进行的那样[104]。
范围。在这篇综述中，我们深入研究了现实世界超图挖掘的广泛研究领域，目的是提供对该领域当前状态的全面分析。我们的综述涵盖了超图挖掘的各个方面，包括超图的数据挖掘工具和度量、结构模式和生成器。对于每种工具或度量，我们解释了其背后的直觉及其与以前概念的联系。我们为结构模式和生成器提供了全面的分类。对于结构模式，我们首先根据是否考虑时间演变将它们分为静态模式和动态模式。之后，我们根据每个模式定义的最小元素，进一步将模式划分为节点级别、超边级别、子超图级别和超图级别。对于生成器，我们首先根据它们是生成整个超图还是子超图将它们分为全超图生成器和子超图生成器。之后，我们根据它们是生成静态超图还是动态（即，时间）超图，将生成器细分为静态和动态的。我们对生成器进行了系统比较，不仅考虑了它们的输出，还考虑了它们的要求以及它们再现特定结构模式的能力。值得注意的是，这篇综述侧重于在现实世界超图中出现的模式和为再现这些现实世界模式而设计的生成器。没有在现实世界超图上明确验证的数学概念和生成器（例如，[134, 143]）不在本综述的范围之内。
相关综述。现实世界图挖掘领域有着丰富的历史背景，导致开发了许多模式和生成器。Chakrabarti和Faloutsos[26]提供了现实世界图中模式和图生成器的全面概述。Drobyshevskiy和Turdakov[45]以及Bonifati等人[19]专注于图生成器，提供了它们的详细分类。人们对超图的兴趣日益增加。Antelmi等人[7]，Gao等人[55]和Zhang等人[147]系统回顾了超图学习，特别关注了为节点和超边生成嵌入（即，低维向量）的不同方法的分析。一些综述关注了超图的应用，包括可视化[51]和划分[22]。Torres等人[130]广泛探讨了不同的数学框架，包括超图，用于表示高阶复杂系统。同样，Battiston等人[15]从动态系统和随机过程的角度，检查了超图作为模拟高阶互动的工具的有用性。在这篇综述中，我们专注于现实世界超图及其结构模式，特别是我们通过提供超图挖掘最新发展的全面概述，并提出分类以增强该领域的理解。
路线图。这篇综述的其余部分组织如下。在第2节中，我们提供了数学背景并介绍了常用的超图数据集。在第3节中，我们介绍了用于数学定义和挖掘超图模式的工具和度量。在第4节中，我们展示了研究人员在现实世界超图中观察到的各种结构模式。在第5节中，我们介绍了旨在再现现实世界超图模式的不同超图生成器。在第6节中，我们讨论了超图挖掘的未来应用和方向。最后，我们在第7节中总结了这篇综述。
2 预备知识
在这一部分，我们为超图提供了数学背景，并讨论了现有文献中使用的现实世界超图数据集。参见表1以了解常用符号。
2.1 数学背景
在一些工作中，子超图的定义更为宽松，我们将为这些情况提供明确的说明。在这篇综述中，我们明确使用 表示超图，并使用 表示我们在讨论（成对的）图。
尽管星形扩展包含了超图中的所有邻接信息，但节点和超边都被统一表示为节点。然而，由于节点和超边的特性不同，这种对称处理可能并不理想[139]。在大多数超图操作、概念和度量中，节点和超边被区分对待，从而打破了这种对称性，这在星形扩展中是做不到的。参见图3，了解上述两种二元投影的示例。
B7. 时序超图。与上面介绍的静态超图相比，时序超图（也称为动态超图）不仅描述了超图的结构信息，还描述了其随时间的演变。
2.2 数据集
表2总结了一些来自现实世界的公开可用且经常使用的超图数据集的基本统计信息。这些数据集按其领域分组，我们为每个数据集中的节点和超边提供了简要描述。
3 工具和度量
在本节中，我们介绍用于超图结构模式的数学定义和挖掘的工具和度量。我们承认存在其他在超图上定义的工具和度量，但尚未应用于实际超图或超图结构模式的分析。在图5中，我们提供了以下我们将介绍的工具和度量的概述分类。
3.1 工具工具包括用于定义和挖掘结构模式的零模型和非平凡概念。
3.1.2 概念。概念包括为超图的分析和解释提供指导的基本思想和理论。它们帮助我们揭示现实世界超图的潜在结构和/或时间模式
C1. 开放和封闭三角形。三角形（即三节点团）在成对图中是一个重要的基本元素，因为它们用来测量各种结构属性，如社区结构[127]和传递性[63]。在超图的背景下，三角形可以被分类为开放和封闭的，描述三个节点之间不同类型的高阶交互[16]。如图6(b)所示，在开放三角形中，每对节点在一个或多个超边中共同出现，但所有三个节点不共享任何超边。相反，在封闭三角形中，所有三个节点至少在一个超边中共同出现。值得注意的是，这个概念也可以扩展到更高阶。例如，考虑图6中说明的超图。在这个超图中，节点2、3和5形成一个开放三角形，而节点3、5和8形成一个封闭三角形。重要的是，封闭三角形要求至少有一个超边包含三个节点，这在成对图中无法定义。这使得封闭三角形的概念能够捕捉超图独有的高阶局部结构。
C2. 高阶网络模式（HO-motifs）。在成对图中，可以通过分析网络模式的出现来研究局部子结构，这些模式也被称为图块[101, 102]。网络模式是结构相同的子图的类别，描述了一组节点之间的连接模式。高阶网络模式（HO-motifs）是网络模式到超图的自然推广，它们表征涉及群体交互的局部子结构[93, 94]。具体来说，给定一组𝑘个节点，涉及这𝑘个节点的HO-motifs由它们之间存在的大小为2，...，𝑘的超边来定义。注意，在定义中不考虑包含𝑘个节点以外的节点的超边。例如，在图6(c)中，我们在图6(a)的超图中提取了由三节点组{1, 2, 3}和{2, 4, 5}形成的两个HO-motifs实例。这两个实例根据一个大小为2的超边在一个大小为3的超边内部的存在在结构上有所区分。Juul等人[65]提出了一个相关概念，其中在模式中只考虑最大超边。
C3. 超图模式（H-motifs）。虽然网络模式和高阶网络模式（见C2）描述了固定数量的连接节点的连接模式，但超图模式（H-motifs）专注于三个连接超边的重叠模式[83]。H-motifs是基于对应于由三个集合组成的维恩图中七个部分的空集来定义的。对于三个超边𝑒𝑖、𝑒𝑗和𝑒𝑘，这七个子集是(1) 𝑒𝑖 \ 𝑒𝑗 \ 𝑒𝑘，(2) 𝑒𝑗 \ 𝑒𝑘 \ 𝑒𝑖，(3) 𝑒𝑘 \ 𝑒𝑖 \ 𝑒𝑗，(4) 𝑒𝑖 ∩ 𝑒𝑗 \ 𝑒𝑘，(5) 𝑒𝑗 ∩ 𝑒𝑘 \ 𝑒𝑖，(6) 𝑒𝑘 ∩ 𝑒𝑖 \ 𝑒𝑗，和(7) 𝑒𝑖 ∩𝑒𝑗 ∩𝑒𝑘。参见图6(d)中的H-motifs示例。在这些示例中，不同的子集是非空的（用阴影表示），因此它们的重叠模式是可区分的。假设没有重复的超边，总共可以定义26个独特的H-motifs，直到超边的排列。最近，Lee等人[86]和Niu等人[108]通过考虑不仅七个子集的空集而且它们的基数扩展了H-motifs的概念。此外，Moon等人[103]将这个概念扩展到了有向超图[72]，其中每个超边内的节点被划分为头和尾集合，从而产生了91种不同的模式。
C4. 时序超图模式（TH-motifs）。为了描述三个连接的时序超边的时间动态，除了重叠模式外，还定义了96个时序超图模式（TH-motifs）[84, 85]。从结构的角度来看，TH-motifs遵循H-motifs的概念（见C3），通过考虑H-motifs中使用的相同的七个子集的空集。在时间方面，TH-motifs是为在短时间间隔内发生的三个时序超边定义的，同时考虑了时间局部性。此外，TH-motifs的定义包含了这三个时序超边的相对到达顺序，这允许进一步表征在静态H-motifs中无法区分的模式。
C5. 自我网络。以单个节点为中心的交互通常通过构建自我网络[100]进行分析，其中中心节点称为自我节点（或简称为自我）。自我网络模型化了自我节点𝑢与其邻居（称为alter-nodes，或简称为alters）之间的所有交互。Comrie和Kleinberg[37]为给定的超图𝐻 = (𝑉, 𝐸)和一个自我节点𝑢 ∈ 𝑉定义了三种不同类型的自我网络：
- 星形自我网络（见图7(b)）𝐻^*(𝑢;𝐻) = (𝑉^*(𝑢;𝐻), 𝐸^*(𝑢;𝐻))由包含自我节点𝑢的所有超边组成，即𝐸^*(𝑢;𝐻) = {𝑒 ∈ 𝐸 : 𝑢 ∈ 𝑒}，并且𝑉^*(𝑢;𝐻) = ⋃{𝑒' ∈ 𝐸^*(𝑢;𝐻)}𝑒'。Alter-nodes集合定义为A(𝑢;𝐻) = 𝑉^*(𝑢;𝐻) \ {𝑢}。
- 径向自我网络（见图7(c））𝐻^†(𝑢;𝐻) = (𝑉^†(𝑢;𝐻), 𝐸^†(𝑢;𝐻))进一步包含由𝑢的alters组成的超边。具体来说，𝐸^†(𝑢;𝐻) = {𝑒 ∈ 𝐸 : 𝑒 ⊆ A(𝑢;𝐻) ∪ {𝑢}}，并且𝑉^†(𝑢;𝐻) = 𝑉^*(𝑢;𝐻)。如图7(c)所示，红色超边由两个没有自我节点的alters组成，因此不在星形自我网络中，但在径向自我网络中。
- 收缩自我网络（见图7(d)）𝐻^‡(𝑢;𝐻) = (𝑉^‡(𝑢;𝐻), 𝐸^‡(𝑢;𝐻))进一步包含不仅包含alters而且还包含其他非alters的超边。更准确地说，这样的超边是通过只取它们中的alter-nodes子集来包含的。形式上，𝐸^‡(𝑢;𝐻) = 𝐸^†(𝑢;𝐻) ∪ {𝑒 ∩ A(𝑢;𝐻): 𝑒 ∈ 𝐸}，并且𝑉^‡(𝑢;𝐻) = 𝑉^†(𝑢;𝐻)。如图7(d)所示，蓝色超边是通过从图7(a)中的超集超边取alter-nodes子集获得的。这个蓝色超边既不在星形自我网络中，也不在径向自我网络中，但包含在收缩自我网络中。
对于每个alter-node 𝑎 ∈ A(𝑢;𝐻)，我们定义alter-network 𝐻𝐴(·)(𝑎;𝑢, 𝐻) = (𝑉𝐴(·)(𝑎;𝑢, 𝐻), 𝐸𝐴(·)(𝑎;𝑢, 𝐻))，它只包含𝐸(·)(𝑢;𝐻)中包含𝑎的超边。不同类型的自我网络有不同的alter-network。形式上，𝐸_𝐴^𝑋(𝑎;𝑢, 𝐻) = {𝑒 ∈ 𝐸_𝑋(𝑢;𝐻): 𝑎 ∈ 𝑒}, ∀𝑋 ∈ {𝑆, 𝑅,𝐶}。
C6. 多级分解。为了降低超边大小灵活导致的超图复杂性，将超图通过（连接）每个超边中的每对节点（即，使用团扩展）转换为成对图是一种常见的方法。然而，正如第2节所讨论的，团扩展可能会导致大量信息丢失，这激发了开发更准确转换方法的动力，以保留更高阶信息。给定超图𝐻 = (𝑉, 𝐸)的多级分解[43]提供了一系列𝑘级分解图，其中𝑘 ∈ {1, · · · , max𝑒∈𝐸 |𝑒|}。形式上，给定一个超图𝐻和一个级别𝑘，𝑘级分解图是𝐺(𝑘) = (𝑉(𝑘), 𝐸(𝑘))，其中𝑉(𝑘) = {𝑣(𝑘) ⊆ 𝑉 : |𝑣(𝑘)| = 𝑘 且 ∃𝑒 ∈ 𝐸 s.t. 𝑣(𝑘) ⊆ 𝑒}，并且𝐸(𝑘) = {(𝑢(𝑘), 𝑣(𝑘)) ∈ 𝑉(𝑘)^2 : ∃𝑒 ∈ 𝐸 s.t. 𝑢(𝑘) ∪ 𝑣(𝑘) ⊆ 𝑒}。也就是说，在𝑘级分解图𝐺(𝑘)中，每个节点𝑣(𝑘)代表至少在一个超边中共同存在的𝑘个节点的子集，如果至少有一个超边包含它们的并集，则连接两个节点（即，子集）𝑢(𝑘)和𝑣(𝑘)。参见图8多级分解的示例。直观地说，𝑘级分解图描述了大小为𝑘的节点组如何相互作用。值得注意的是，超图𝐻的1级分解图等同于𝐻的团扩展。
C7. 高阶连通性。Kim和Goh[70]探索了将超图转换为成对图的另一种方法。具体来说，给定一个超图𝐻 = (𝑉, 𝐸)和一个阈值𝑚，他们提出构建一个图描述𝐻的高阶连通性，其中每个超边𝑒 ∈ 𝐸映射到
中的一个节点，并且两个节点𝑒1 ∈ 𝐸和𝑒2 ∈ 𝐸在
中相邻，当且仅当它们至少共享𝑚个公共节点，即
，其中
= {(𝑒1, 𝑒2): 𝑒1, 𝑒2 ∈ 𝐸, |𝑒1 ∩ 𝑒2| ≥ 𝑚}。
C8. 封装。LaRock和Lambiotte[79]提出了超图中封装的概念。封装是重叠的一种特殊情况。具体来说，如果一个超边𝑒1被另一个超边𝑒2完全包含，即𝑒1 ⊆ 𝑒2，则称超边𝑒1被超边𝑒2封装。
C9. 超核心。在成对图上具有各种应用（例如，社区检测、图可视化和文本分析；见[99]的调查）的𝑘-核心的凝聚子图模型的概念已被扩展到超图。我们将这些扩展概念统称为超核心。有几种变体[9, 21, 91, 115]，我们关注于基于此模式探索实际超图的变体。Bu等人[21]提出的(𝑘, 𝑡)-超核心概念使用了比我们在定义2.1中更一般化的子超图定义。具体来说，(𝑘, 𝑡)-超核心的概念不仅允许超边集是原始集合的子集（如在定义2.1中），还允许每个超边是原始超边的子集。也就是说，如果对于每个超边𝑒' ∈ 𝐸'，我们可以找到一个不同的（即，对于不同的𝑒'，𝑒也不同）超边𝑒 ∈ 𝐸使得𝑒' ⊆ 𝑒（而不是要求𝑒' = 𝑒）。给定一个超图𝐻 = (𝑉, 𝐸)，𝑘 ∈ N，和 𝑡 ∈ [0, 1]，𝐻的(𝑘, 𝑡)-超核心被定义为最大的广义子超图，其中每个节点至少在𝑘个超边中，并且每个超边至少包含其原始组成节点的𝑡比例（至少两个）。
C10. 超图社区。社区的概念（即，内部连接密集且与外部节点相对稀疏连接的节点组）已在成对图上得到了广泛研究[52]。该概念已被扩展到超图[2, 118, 145]。在超图中，社区是节点组，同一社区内的节点更有可能一起形成超边，与属于不同社区的节点相比。
3.2 度量
度量是用于定义和挖掘超图模式的数量。通常，我们根据特定度量将实际超图与由零模型生成的随机超图进行比较，并展示显著的数值差异。
M1. 组度。如第2.1节所讨论的，超图中一个节点的度被定义为包含该节点的超边数量。这个概念自然扩展到节点组，并可用于研究组内成员出现之间的相互关系。具体来说，给定一个超图𝐻 = (𝑉, 𝐸)，节点组𝑆 ⊆ 𝑉的组度𝑑(𝑆;𝐻)定义为包含整个节点组的超边数量，即𝑑(𝑆;𝐻) = |{𝑒 ∈ 𝐸 : 𝑆 ⊆ 𝑒}|。
M2. 超核心性。基于超核心的任何定义（见C9），我们可以有相应的超核心性度量，类似于成对图中核心性的概念。由于我们特别关注(𝑘, 𝑡)-超核心的概念[21]（见C9），我们在这里介绍相应的𝑡-超核心性定义。给定一个超图𝐻 = (𝑉, 𝐸)和𝑡 ∈ [0, 1]，节点𝑣 ∈ 𝑉的𝑡-超核心性，记为𝑐𝑡(𝑣)，是𝑣在(𝑘*, 𝑡)-超核心中的最大𝑘*。一个节点的超核心性本质上量化了每个节点在超图中的中心位置程度。它已被用于估计超图上传播模型中节点的影响力[21]，以及与其他度量一起用于检测异常节点[42]。
M3. 超边同质性。超边同质性量化了一起形成超边的节点之间的结构相似度[81]。具体来说，给定一个超图𝐻 = (𝑉, 𝐸)，超边𝑒 ∈ 𝐸的超边同质性定义为：homogeneity(𝑒;𝐻)= 。它对应于超边内节点对共享的超边的平均数量，本质上量化了其组成节点之间的结构相似度。该定义可以通过考虑超出对的更大的节点子集来扩展。
M4. 传递性。在成对图中，一个节点的两个邻居相互连接的比例被称为传递性或聚类系数。已经提出了几种扩展方法来衡量群体交互的传递性。我们重点关注HyperTrans，这是一种因其理论优势和在分析现实超图中的实用性而闻名的传递性度量。它基于超楔（即相交超边对）定义。给定一个超图𝐻 = (𝑉, 𝐸)，超楔𝑤 = {𝑒𝑖, 𝑒𝑗}的传递性定义为：
其中，左翼𝐿(𝑤) = 𝑒𝑖 \ 𝑒𝑗，右翼𝑅(𝑤) = 𝑒𝑗 \ 𝑒𝑖，𝑓(𝑤, 𝑒)代表计算某个超边对这两个翼之间的交互强度的函数。超图的传递性是所有超楔的平均传递性值。
M5. 特征轮廓(CPs)。为了更好地分析给定超图的结构属性，我们可以同时检查多个感兴趣的结构模式（如H-模体）来构建超图的特征轮廓(CP)。首先，我们获取每种模式的数值频率，例如对于H-模体，我们可以简单地统计其实例数。然后，通过将这些模式在给定超图中的频率与随机超图中的频率进行比较，我们可以确定它们的统计显著性。形式上，给定超图𝐻，设𝑃表示感兴趣的模式集，模式𝑝 ∈ 𝑃的显著性定义为：
M6. 密度。对于成对图，密度定义为边数与节点数的比值，是衡量边连接度的广泛使用的指标。许多应用问题，如社交媒体中的欺诈检测、众包框架中的专家搜索以及生物模块检测，都被表述为识别高密度子图的任务。密度的概念自然延伸到（子）超图。具体来说，给定一个超图𝐻 = (𝑉, 𝐸)和超边的子集E ⊆ 𝐸，E的密度𝜌(E)定义为： 。 这个指标是超边数量与节点数量的比值，随着在固定节点集内形成更多超边而增加。值得注意的是，该指标并未考虑超边的大小。
M7. 重叠度。密度（见M6）提供了一种直观的方式来衡量超边之间的重叠程度。然而，密度的定义忽略了超边大小的影响，导致某些情况下的结果与直观预期不一致。例如，考虑图9中的例子，直观上预期E1中的超边相比E2具有更多的重叠，但E1和E2具有相同的密度。Lee等人提出了重叠度作为一种替代指标，额外考虑了单个超边的大小。对于给定的超图𝐻 = (𝑉, 𝐸)和超边的子集E ⊆ 𝐸，E的重叠度𝑜(E)定义为： 。E的重叠度等价于由E中的边组成的子超图中的平均节点度。与我们的直觉一致，图9中的E1相比E2具有更高的重叠度。
M8. 模块度。为了评估成对图中社区结构的强度，Newman引入了模块度的概念。较高的模块度值表明社区内的节点对更可能有边连接，而不同社区的节点对之间较少有边连接，从而暗示了强社区结构。模块度的概念已多次扩展到超图。我们介绍Kamiński等人和Giroire等人使用的定义，它们用于探索现实超图中的模式和设计超图生成器。给定超图𝐻 = (𝑉, 𝐸)和一组社区S，使得。
其中，𝐸𝑆是完全包含在社区𝑆内的超边集，𝐸𝑘是大小为𝑘的超边集，𝑣𝑜𝑙(𝑆;𝐻)是社区𝑆中节点的度的总和。基于此，𝐻的模块度定义为：
M9. 持续性。一个节点组可能在多个超边中多次共现（例如，频繁共同购买的商品）。节点组的持续性概念量化了它们随时间的共现一致性。正式地，给定一个超图𝐻 = (𝑉, 𝐸)和一段时间范围𝑇，节点组𝑆 ⊆ 𝑉的持续性定义为：
M10. 平均交集大小。给定一个按时间顺序排列的超边序列 𝑆𝐸 = (𝑒1, 𝑒2, ... , 𝑒𝑘 )，平均交集大小定义为[37]： 𝐼(𝑆𝐸) = (Σ𝑘𝑖=1 |𝑒𝑖∩𝑒𝑖+1|) / (𝑘−1), 即该指标计算连续超边之间交集的平均大小，与时间变化的平滑程度相关。
M11. 有效直径。为了评估（超）图的整体连通性，我们可以使用直径的概念[137]，它被定义为所有节点对之间最短路径的最长长度（见B3）。基于此，提出并使用了有效直径的概念[87]，即最短路径长度在至少 𝑃eff%（例如𝑃eff = 90）节点对之间不超过 𝑑 的最小距离。同样的定义也适用于超图[77]。当少数节点对之间的最短路径极长时，有效直径在数值上更加稳健。
4 结构模式
在本节中，我们介绍实际超图中的结构模式。也就是说，我们展示跨不同领域建模现实世界系统的超图的常见结构特征。我们将结构模式分类如下：
• 静态和动态模式。静态模式描述静态超图或时间超图的单个快照（见B7）的特征，而动态模式描述时间超图随时间的演变。
• 节点级、超边级、子超图级和超图级模式。
模式的级别取决于用于定义模式的基本元素。如果一个模式描述了单个节点（或超边）的某些属性，则将其归类为节点级（或超边级）模式。描述整个超图属性的模式被称为超图级模式。在特定组合的节点和/或超边上定义的模式被归类为子超图级模式。
这两种分类形式是正交的，通过它们的组合形成了总共八个子类别。在图10中，我们提供了我们将在下文介绍的结构模式的分类概述。本节重点描述观察到的模式，而不深入探讨它们背后的原因。在第5节中，我们旨在通过简单的机制再现它们来揭示潜在的解释。
4.1 静态模式
我们首先介绍静态模式。这些模式描述了节点和超边的结构属性，以及现实世界超图的整体特征。静态模式不包括与时间变化相关的那些。
4.1.1 节点级模式。我们将研究与单个节点属性相关的静态模式，这些是超图中的基本元素。
P1. 重尾度分布。现实世界超图的度分布（见B4）通常呈现重尾分布[77]，主要是幂律分布（见B5）。这表明少数节点参与了异常大量的群体交互，而大多数节点只参与少数交互。在成对图上也观察到了类似的模式，它们（部分）由“富者愈富”[49]解释，这表明了一个时间过程，其中度较高的节点随着时间的推移更有可能更快地增加其度。度数高的少数节点被称为枢纽节点[14]，它们在许多应用中扮演着重要角色。
P2. 重尾超核心性分布。对于一个节点，它的度可以看作是它的中心性度量，它的超核心性（见M2）也是如此。Bu等人[21]观察到，在现实世界的超图中，节点的超核心性通常呈现重尾分布（见B5）。这意味着涉及少数节点的高度密集的子超图，而大多数节点不属于这样的子超图。超核心性在成对图中的对应概念核心性，也已知在现实世界的图中通常呈现重尾分布[123]。
P3. 核心-外围结构。许多现实世界的超图具有核心-外围结构，其中我们有核心节点和外围节点。大量超边应该在核心节点之间形成，而外围节点彼此之间连接不好（即，不在许多超边中共同出现），并且应该主要在至少有一个核心节点出现的超边中共同出现[5, 110, 132]。成对图中的类似结构也已被研究[20]。
4.1.2 超边级模式。现在我们将研究超边级的静态模式。就像节点一样，超边也是超图中的基本结构元素（见B1）。因此，检查超边级模式让我们能够从不同角度洞察现实世界超图的结构特征。
P4. 重尾大小分布。成对图和超图之间的一个基本区别在于，超边的大小是可变的，可以连接任意数量的节点，而成对图中的边只能连接两个节点。因此，超边的一个关键属性是它们的大小，即在超边内共同出现的节点数量。现实世界超图中的超边大小分布往往遵循重尾分布[77]（见B5）。这意味着存在大量小尺寸的超边，同时也经常存在非常大的超边。
P5. 高同质性。超边的同质性（见M3）衡量超边内节点在结构上的相似度。Lee等人[81]观察到，现实世界超图中的超边往往比通过HyperCL模型（见C3）获得的随机超图中的超边具有显著更高的同质性。这种模式表明，现实世界的超边更可能由结构相似的节点填充，而不是随机选择的节点。
P6. 显著的封装。LaRock和Lambiotte[79]通过将现实世界的超图与随机超图进行比较来研究封装（见C8），在随机超图中，相同大小的超边被分组在一起，每个超边组内的节点标签被随机排列。这保留了相同大小超边之间的重叠模式，同时随机化了不同大小超边之间的模式。他们观察到，现实世界超图中的超边往往表现出比相应随机超图中更高的封装程度（即，封装出现的频率更高）。这种模式突出了现实世界超图中超边之间高度互联的方面。
4.1.3 子超图级模式。现在我们将研究子超图级的静态模式。子超图级模式既不是关于单个节点/超边的，也不是关于整个超图的。相反，它们定义在节点和/或超边的组合上，例如，节点子集和超边对。
P7. 重尾组度分布。我们已经看到现实世界超图中（单个）节点度的重尾分布的存在（见P1）。现在我们深入研究现实世界超图中节点组的度分布（见M1）。几个研究者研究了组度的分布：
• 通常，节点子集的组度是包含子集中所有节点的超边数量。Benson等人[17]观察到，现实世界超图中的节点对和三元组的平均度显著高于通过配置模型（见N1）获得的随机超图。此外，Lee等人[81]观察到，现实世界超图中的节点对或三元组的度分布比通过HyperCL（见N3）获得的随机超图具有更厚的尾部。这表明现实世界超图中频繁共同出现的节点组的普遍性。
• Do等人[43]使用多级分解（见C6）研究了组度，并观察到对于不同的𝑘值，𝑘级分解图的度分布是重尾的。注意，𝑘级分解图中的节点度与组度相关，但并不等同于组度。
上述模式也可以用 “富者愈富 ”来解释（见 P1；另见 G6）。
P8. 重尾交集大小分布。我们已经看到现实世界超图中的（单个）超边大小遵循重尾分布（见P4）。现在我们扩展到超边对并研究超边交集。研究超边交集允许我们从不同的角度研究超图的连通性。Kook等人[77]观察到，现实世界超图中的超边对的交集大小分布遵循重尾分布。此外，他们还观察到现实世界超图中的一些超边对共享大量公共节点（即，大交集），这在通过随机填充模型（见N2）生成的随机超图中无法观察到。
P9. 显著的高阶连通性。Kim和Goh[70]从另一个角度研究超边交集。他们提出构建图来描述具有不同阈值𝑚的超图的高阶连通性（见C7），其中每个超边在构建的图中被表示为一个节点，如果两个相应的超边至少共享𝑚个公共节点，则构建图中的两个节点相邻。他们观察到，现实世界超图倾向于在更高的𝑚值下保持大的连通分量，而在通过配置模型（见C1）获得的随机超图中则不是这样，这表明现实世界超图中存在显著的超边交集，这与上述观察结果一致（见P8）。
P10. 高传递性。几位研究者已经从不同角度研究并扩展了超图的传递性（见M4），观察到现实世界超图中的高传递性：
• Kim等人[71]使用他们提出的度量HyperTrans（见M4）分析传递性。他们观察到，与通过HyperCL模型（见C3）获得的随机超图相比，现实世界超图倾向于表现出显著更高的传递性。
• Do等人[43]研究了现实世界超图的多级分解图（见C6）中的聚类系数。他们观察到，每个分解图的聚类系数在现实世界超图中显著高于通过随机填充模型（见N2）生成的随机超图。
• Ha等人[59]从节点的角度研究了现实世界超图的局部聚类系数。具体来说，他们考虑了每个节点𝑣的四元组聚类系数，该系数定义为与𝑣相关的实际四元组数量与𝑣可能的最大四元组数量的比率，其中每个与𝑣相关的四元组以(𝑣, 𝑣', 𝑒1, 𝑒2)的形式出现，𝑣 ≠ 𝑣' ∈ 𝑉，𝑒1 ≠ 𝑒2 ∈ 𝐸，且{𝑣, 𝑣'} ⊆ 𝑒1 ∩ 𝑒2。他们观察到，现实世界超图中的平均局部聚类系数显著高于通过类似于随机填充模型（见N2）或配置模型（见N1）的模型生成的随机超图。
这些模式通常意味着（节点组）如果它们有共同的邻居，就更有可能在超边中共同出现。
P11. 高度重叠的自我网络。超图的密度（见M6）或重叠度（见M7）衡量其超边相互重叠的程度。Lee等人[81]观察到，在星形自我网络（见C5）中，现实世界超图的星形自我网络的密度和重叠度显著高于通过HyperCL模型（见C3）获得的随机超图。这意味着现实世界超图的超边比随机对应物更局部重叠，这也与高传递性（见P10）有关。
P12. 社区结构。社区（见C10）在现实世界的超图中普遍存在，Girire等人[56]使用扩展的模块化概念（见M8）数值地展示了社区结构的强度。Contisciani等人[38]观察到现实世界超图中重叠社区的普遍性，并提出了一种统计方法来检测这种社区。Lotito等人[95]进一步观察到现实世界超图中存在层次（即，社区进一步划分为更小的社区）和多尺度（即，社区存在于不同尺度上）的社区结构。值得注意的是，Torres等人[130]指出，相同原始数据的不同超图表示可能会显示不同的社区结构。
P13. 模式的强大表征能力。几种度量和模式可以作为超图的有效表征工具。具体来说，现实世界的超图来自不同的领域（或领域；见表2），同一领域内的超图通常在某些度量和模式上观察到相似，而不同领域的超图则相对不相似。
• Benson等人[16]使用开放和封闭三角形的数量（见C1）来表征现实世界的超图。具体来说，开放三角形数量与封闭三角形数量的比率是区分不同领域超图的有用指标。
• Lotito等人[94]使用高阶网络模式（HO-motifs；见C2）的频率来表征现实世界的超图。具体来说，同一领域内的超图显示出HO-motifs归一化计数的相似分布，而不同领域的超图则显示出显著差异。Juul等人[65]观察到关于𝑚-模式（见C2）分布的类似现象。
• Lee等人[83]使用H-motifs（见C3）构建现实世界超图的特征配置文件（CPs；见M5）。这些CPs基于H-motifs总结局部结构模式，不同领域的真实世界超图根据CPs明显区分开来。
• LaRock和Lambiotte[79]观察到，同一领域内的超图显示出相似的封装相关模式（例如，封装程度如何随着超边大小的变化而变化），而不同领域的这种模式则不同。
结构模式的强大表征能力进一步验证了它们作为分析现实世界超图的工具的有用性和意义。此外，结构模式还可以用作机器学习的结构特征[16, 83–86]，用于各种下游应用（见第6.2节）。
4.1.4 超图级模式。现在我们将研究超图级的静态模式。超图级模式涉及超图整体的属性，检查它们为我们提供了对现实世界超图的宏观洞察。
P14. 偏斜的奇异值分布。对现实世界超图的不同矩阵表示进行奇异值分解（SVD）可以提供关于超图结构属性的重要见解。具体来说，检查奇异值分布的偏斜程度可以提供有关超图内层级和社区结构（见P12）的信息，就像研究人员对成对图所做的那样[44, 68, 120]。
• 对于现实世界超图的关联矩阵（见B2），观察到奇异值分布的偏斜（即，当我们按降序排列奇异值时，值显著减小）[77]。
• Do等人[43]考虑了使用多级分解（见C6）的矩阵表示方式，并观察到现实世界超图的每个𝑘级分解图的邻接矩阵的奇异值偏斜。
奇异值的大小反映了相应节点（对于关联矩阵）或节点组（对于多级分解图的邻接矩阵）的结构重要性（例如，影响力）。因此，上述观察表明，现实世界超图中的一些节点或节点组比其他节点或节点组更为普遍和有影响力。
4.2 动态模式
现在我们介绍动态模式。给定一个时间超图，动态模式描述超图及其内部的时间演变或变化。
4.2.1 超边级动态模式。我们现在研究超边级的动态模式，描述超边出现之间的时间关系。
P15. 频繁的超边重复。在各种系统中，过去事件的重现是普遍存在的。超边重复，即过去超边的重现，也已在现实世界超图的演变中观察到。
• Benson等人[17]观察到，在现实世界时间超图的演变过程中，许多超边会反复出现。
• Lee和Shin[84, 85]进一步观察到，现实世界时间超图中超边重复次数的分布通常遵循重尾分布。
• Lee和Shin[84, 85]还观察到，与随机超图相比，超边重复在现实世界超图中发生得更频繁（即，同一超边两次出现的间隔时间更短）。随机超图是通过使用HyperCL（见N3）生成的，并且超边的时间戳是从原始时间戳中随机重排的。
• Cencetti等人[24]使用了突发行为（即，同一超边在短时间内多次重复）的概念，并观察到突发行为在现实世界超图中比在随机超图中更为普遍，随机超图是通过随机洗牌相同大小的时间超图的时间戳获得的。
上述工作的作者普遍观察到，与随机对应物相比，超边重复在现实世界超图中更为常见，尤其是对于大型超边。
P16. 时间局部性。在成对图的演变中，时间局部性指的是新交互更类似于最近的交互而不是旧交互的倾向[80, 98]。
检查超边的结构相似性与它们在现实世界超图中发生的时间之间的关系，也揭示了时间局部性的存在。
• Benson等人[17]观察到，新出现的超边更有可能与较近过去的超边共享公共节点，而不是与较远过去的超边共享。
• 对于每对节点𝑣1和𝑣2，以及每个超边大小𝑘，Gallo等人[54]计算并比较了在不同时间步骤中包含𝑣1和𝑣2的𝑘大小超边的数量。他们观察到时间相关性，其中上述相同对的数字在时间上接近的时间步骤之间在数值上相似。这种时间相关性存在于不同的超边大小中。
除了整个超边的重复行为（见P15），时间局部性，关于超边内子集的重复，为时间超图演变提供了独特的见解。
P17. 时间强化。随着时间超图的演变，新超边的组成受到先前超边的影响。时间强化现象描述了先前超边如何影响新超边的组成。具体来说，Cencetti等人[24]观察到，如果一组节点在过去多次在多个超边中共同出现，那么这组节点在未来更有可能继续在一些超边中共同出现，并且随着过去共同出现期的长度增加，这种可能性会增加。这种模式允许我们分析群体交互的时间稳定性。
4.2.2 子超图级动态模式。我们现在研究子超图级的动态模式。这些模式描述了节点和/或超边组合的时间行为。
P18. 幂律持久性。在现实世界的时间超图中，同一组节点可能在多个超边中随时间共同出现。节点组的持久性量化了它们随时间一致共同出现的程度（见M9）。Choo和Shin[33]观察到，在现实世界的时间超图中，持久性（具体来说，持久性的值与具有该持久性值的节点组数量）通常遵循幂律分布。这种模式意味着总体上，大多数节点组具有低持久性值，但也存在少数节点组具有异常高的持久性。这种模式与上述超边级模式（见P15-P17）相关。然而，它提供了一个不同的视角，通过考虑超边内的组成节点组，而不是整个超边。
P19. 单纯形闭合。单纯形闭合的概念将成对图中的三元闭合[126]概念扩展到超图，提出了形成封闭三角形（或更高阶对应物）的可能机制（见C1）。Benson等人[16]检查了现实世界超图中三个节点之间封闭三角形的出现（即，单纯形闭合事件的发生）与它们在团扩展中的成对连接之间的关系（见B6）。值得注意的是，他们通过计算团扩展中的边重复来考虑边权重，即，他们计算了每对节点共同出现的超边数量。他们观察到单纯形闭合的存在，即，随着团扩展中考虑节点之间连接的数量和/或权重的增加，单纯形闭合事件的可能性趋于增加。这种模式可以很容易地用于超边预测[16]，扩展了三元闭合在链接预测中的效用[62]。
P20. 自我网络中的时间局部性。识别现实世界超图中自我网络（见C5）的时间增长模式是理解和预测围绕单个节点的群体交互动态的重要步骤。就像个别超边的演变表现出时间局部性（见P16）一样，自我网络的演变也显示出时间局部性。
• Comrie和Kleinberg[37]观察到，在自我网络中，时间戳更接近的超边也倾向于表现出结构相似性，共享大量节点。具体来说，他们通过自我网络中时间上连续边的平均交集大小（见M10）来衡量结构相似性。此外，他们观察到随着自我网络的演变和随时间增长，这种结构相似性会降低。
• 他们还从alter-network（见C5）的角度探索了时间局部性，并观察到alter-network内两个连续超边之间的平均时间间隔比通过随机洗牌超边顺序获得的随机超图要短。
与整个超图中超边的时间局部性（P16）相比，自我网络内的时间局部性为局部超图演变提供了独特的见解。
P21. 自我网络的人类原则。回想一下，径向和收缩自我网络可能包括仅由alter-nodes组成的超边，而不包括自我节点（见C5）。因此，这样的自我网络的形成可能在自我节点参与之前就已经开始了。
Comrie和Kleinberg[37]探索了自我节点进入其自我网络的时间。
• 在收缩自我网络中，我们经常观察到自我节点的到达时间和自我网络的大小之间存在近乎完美的正相关。具体来说，如果自我网络较大，自我节点更有可能晚些时候出现。此外，与通过随机洗牌超边顺序获得的随机自我网络相比，自我节点在现实世界的收缩自我网络中更倾向于晚些时候出现。
• 在径向自我网络中，也经常出现类似的但相对较弱的趋势。在径向自我网络中，即使它们的规模相当大，自我节点通常也会在第五个超边引入之前出现。此外，与收缩自我网络一样，自我节点在现实世界的径向自我网络中比在通过随机洗牌超边顺序获得的随机自我网络中更倾向于晚些时候出现。
这些模式为自我网络构建的潜在机制提供了见解，被称为自我网络的人类原则，类似于人类研究史前历史的方式。
P22. 自我网络的新颖率模式。自我网络中新添加的超边可能包含以前未在自我网络中出现过的新节点。这些新节点的数量被称为新颖率。Comrie和Kleinberg[37]研究了新颖率如何随着自我网络的演变而变化。
• 在星形和径向自我网络中，平均新颖率逐渐下降，直到某个点。之后，新颖率几乎保持不变（对于径向自我网络），甚至显示出上升趋势（对于星形自我网络）。
• 在收缩自我网络中，平均新颖率随时间持续下降。
这些新节点总体上难以预测，并且与许多实际问题相关，例如冷启动[121]。理解这些节点出现背后的机制在理论和实践上都具有意义。
P23. TH-motifs的强大表征能力。时序超图模式（TH-motifs；见C4）是静态超图中定义的超图模式（H-motifs）的时间扩展。通过计算给定时间超图中每种96种TH-motif的实例数量，可以将时间超图的结构和时间模式总结为一个96维向量，称为关于TH-motifs的特征配置文件（CP；见M5）。利用CPs，可以有效地区分来自不同领域的时间超图，这种区分比仅使用静态信息的H-motifs进行区分更清晰[84, 85]。这证明了TH-motifs在通过捕获时间和结构模式来表征时间超图方面的有效性。
4.2.3 超图级动态模式。我们现在研究超图级的动态模式。这些模式描述了超图整体特征随时间的变化。
P24. 重叠减少。Kook等人[77]研究了现实世界时间超图中超边的结构互联性如何随时间演变。具体来说，他们观察到所有超边对中相交超边对的比例趋于随时间减少。这一观察与发现超边之间的相似性随着它们出现时间间隔的增加而减少（见P16）的发现一致。
P25. 密集化。在成对图中，密集化的特征是图的密度（见M6）随时间增加，由Leskovec等人[88]观察到。具体来说，他们观察到边的数量与节点数量呈超线性增长（即，，其中𝛼 > 0），因此密度
随着图的增长而增加。Kook等人[77]在现实世界超图的演变中观察到类似的趋势，其中超边的数量与节点数量呈超线性增长，因此现实世界超图的密度也随着它们规模的增长而随时间增加。
P26. 直径缩小。直径缩小是现实世界成对图中观察到的另一种模式[88]，其中有效直径（见M11）通常随着图的增长而减少。这种趋势可以自然地扩展到超图，Kook等人[77]确实在现实世界超图的演变中观察到了这种趋势。这表明，随着现实世界超图规模的扩大，信息或影响力可能更快速地传播。
5 生成器
在本节中，我们介绍超图生成器。我们关注基于现实世界超图属性的生成器。我们承认还有其他不基于现实世界模式的超图生成器，例如深度生成模型和数学模型。
我们将感兴趣的生成器分类为：
• 全超图和子超图生成器。
全超图生成器生成整个超图，而子超图生成器生成超图的部分。
• 静态和动态生成器。静态生成器生成静态超图，而动态生成器生成动态图（即，时间超图；见B7）。值得注意的是，在一些工作中，作者没有明确提到所提出的生成器是生成静态超图还是动态超图。对于这种情况，我们根据生成过程是否可以被解释为具有时间依赖性的演变过程来进行分类。例如，基于优先连接的生成器可以自然地被解释为演变过程，而使用节点洗牌或重连的生成器则不能。
这两种分类方式是正交的，因此我们总共有四个子类别。
对于每个生成器，我们提供其算法过程的总结，包括直觉和讨论（如果有的话）。见表3，了解每个生成器的详细输入和输出。
5.1 全超图生成器
我们首先介绍全超图生成器。全超图生成器接受一些超图统计数据作为输入（通常还带有一些模型特定的超参数），并输出一个整体的超图，该超图应该保留现实世界超图中的一些结构模式。
5.1.1 静态生成器。我们将在下面介绍静态全超图生成器。
G1. HyperLap。由Lee等人[81]提出的HyperLap基于现实世界超图中超边的重叠模式（见P5和P11）。它可以被视为HyperCL（见N3）的多层次扩展，其中扩展有助于再现重叠模式。
• 算法摘要：节点被组织在多个级别中，每个级别都包含所有节点，但粒度不同。具体来说，从上到下，一个级别的每个组在下一个级别中被分成两个组，因此更深层次（即，更接近底部）的级别包含更多的组。在生成每个超边时，HyperLap首先采样一个级别，然后在该级别中选择一个组。选择的组中的节点被采样以填充超边，采样概率与节点的度成正比。
• 直觉：由于超边是基于组生成的，因此同一组内的节点在结构上是相似的，这使得生成的超边具有高同质性（见P5）。由于每个自我网络倾向于包含在许多超边中共同出现的结构相似的节点，每个自我网络的密度（见M6）和重叠度（见M7）自然产生（见P11）。最后，在一个深层次（即，接近底部）的小组中的对或三元组也属于所有更浅层（即，更接近顶部）的级别的同一组，因此它们更经常被选择一起形成超边。因此，更多的超边包含和重叠在这样的对或三元组上，这意味着偏斜的重尾节点对和节点三元组度分布（见P7）。
• 注释：Lee等人[81]还在HyperLap的基础上提出了一个超参数选择方案，该方案还包括了一个自动的过程。
G2. CIGAM。由Papachristou和Kleinberg[110]提出的CIGAM（连续影响者引导附加模型）旨在捕捉现实世界超图中的核心-外围结构（见P3）。
• 算法摘要：每个节点被分配一个声望值，每个潜在的超边独立生成，其中采样概率由组成节点的声望值决定。
• 直觉：具有高声望值的节点应该是“核心节点”。每个生成的超边可能包含核心节点，这意味着核心-外围结构（见P3）。为了减少似然估计中的计算复杂性，只考虑每个潜在超边中的最大声望值。
• 讨论：
- 需要更多的超图生成器来捕捉更多属性，例如模式（见C2和C3）。
- 给节点分配声望值的想法可能与其他生成器结合。
G3. Hyper-𝒅𝑲。由Nakajima等人[105]提出的Hyper-𝒅𝑲系列是超图的参考模型家族，它扩展了成对图的𝑑𝐾系列[97]。它们生成保留节点和超边给定局部属性的超图（例如，P1和P7）。
• 算法摘要：它们使用两个超参数𝑑𝑣 ∈ {0, 1, 2, 2.5} 和 𝑑𝑒 ∈ {0, 1}。较高的𝑑𝑣值意味着保留关于节点度的更高阶信息，而较高的𝑑𝑒值意味着保留关于超边大小的更高阶信息。例如，𝑑𝑣 = 0（或𝑑𝑒 = 0）表示保留平均度（或平均超边大小），𝑑𝑣 = 1（或𝑑𝑒 = 1）表示保留单个节点度（或单个超边大小），𝑑𝑣 = 2表示保留节点对的联合度。𝑑𝑣 ∈ {0, 1}（最多保留度分布）的情况很直接，它们与配置超图模型[31]（见N1）非常相似。对于𝑑𝑣 ∈ {2, 2.5}（保留一些更高阶模式），生成器从𝑑𝑣 = 1开始，然后使用边重连来改进相应的更高阶模式，同时保持度分布。
• 讨论：更高阶模式是通过直接操作（即，边重连）来保留的，这可能效率较低。提出保留这种更高阶模式的局部机制将是一个有趣的未来方向。
G4. RNHM。由Kim等人[69]提出的RNHM（随机嵌套超图模型）旨在控制超边嵌套度（即，封装；见C8和P6）。
• 算法摘要：首先，生成许多大超边及其所有子集。然后，进行重连步骤。在每个重连步骤中，RNHM（1）随机选择一个超边𝑒，以及（2）选择一个节点𝑣 ∈ 𝑒，并随机用最初与𝑣不相连的其他节点替换𝑒中的一些节点（见B3）。选择每个超边的概率和重连步骤的数量是可调的。
• 直觉：在初始状态，嵌套度（即封装；见C8）最大化。每个重连步骤破坏了一些嵌套子结构。调整允许我们控制最终生成超图中的嵌套度。
• 讨论：尽管RNHM已被LaRock和Lambiotte[79]进一步讨论和利用，但如何确定RNHM中的参数以更好地保留观察到的模式仍在等待覆盖。
G5. HOC。由Kim和Goh[70]提出的HOC（高阶连通）基于对现实世界超图中高阶连通性的观察（见P9）。
• 算法摘要：节点预先分配到大小为二的子组中。HOC从一个给定数量的空超边开始，HOC重复以下过程，直到超边的平均大小达到一个给定的数字：HOC首先随机选择一个超边𝑒，然后以概率1-𝑝随机添加一个节点到𝑒中，以剩余概率𝑝将一个随机子组中的所有节点添加到𝑒中。
• 直觉：当𝑝的值增加时，同一子组中的节点经常在多个超边中共存，这导致高阶组件的出现，其中多个超边的交集大小很大（见P9）。
• 讨论：每个节点被分配到一个单一的子组中，而重叠社区[38]（见C10）的想法可能被考虑以提高这个模型的灵活性。
5.1.2 动态生成器。我们现在将介绍动态全超图生成器。
G6. HyperPA。由Do等人[43]提出的HyperPA基于对𝑘级分解图的观察（见P7, P10, 和 P14）。它是优先连接[13]的组扩展，其中关键思想是新节点更有可能附加到现有的高学位节点上，使“富有”的节点“更富有”。例如，共同撰写了许多论文的研究人员可能具有共同的兴趣，这导致了更多的未来合作。
• 算法摘要：对于每个节点𝑣，HyperPA首先采样“新”超边的数量。对于每个“新”超边，HyperPA采样一个超边大小𝑠，然后以与组度（见M1）成比例的概率使用优先连接将节点𝑣附加到大小为(𝑠−1)的组中。
• 直觉：优先连接已知能够产生具有偏斜度分布（见P1）、高聚类系数、小直径等的图。直观地说，HyperPA也产生具有类似模式的超图，这些模式推广到超图（见P7, P10, 和 P14）。值得注意的是，HyperPA中的优先连接是以组方式进行的，这产生了偏斜的组（以及个人）度（见P1和P7）。
• 讨论：HyperPA以动态方式生成超边。然而，在观察和评估中都没有考虑超边的时间戳。将观察和评估扩展到时间超图将是一个有趣的未来方向。
G7. HMPA。由Girire等人[56]提出的HMPA（高模块化优先连接）也使用了优先连接的思想。该生成器还考虑了现实世界超图中观察到的具有高模块化（见M8）的社区结构（见P12）。
• 算法摘要：节点被明确地划分为社区（见C10）。在每个时间步骤，要么生成一个新节点并附加到一个社区，要么使用现有节点生成一个新的超边。在生成每个新超边时，HMPA首先采样一组社区，然后确定从每个社区选择的节点数量。在每个社区内，节点以与它们的度成比例的概率被选择，以优先连接的方式进行。
• 直觉：通过划分节点直接施加社区结构。可以操纵采样概率，以鼓励更多由少数社区甚至单个社区的节点组成的超边，这意味着高模块化。
• 讨论：在这个生成器中，社区是不相交的，社区成员身份是固定的。拥有更灵活的社区结构可能更有益，例如重叠社区[23, 38]（见P12）。
G8. HyperFF。由Kook等人[77]提出的HyperFF基于对现实世界超图演变的观察（见P24, P25, 和 P26）。顾名思义，这个生成器受到成对图上的森林火灾模型[88]的启发。
• 算法摘要：在每个时间步骤，一个新节点加入，一个现有节点被选为大使节点，即“森林火灾”开始的地方。森林火灾通过现有的超边随机传播。当它终止时，从每个被烧毁的节点开始，新的森林火灾开始，这一轮中被烧毁的节点与新节点一起形成一个超边。
• 直觉：作者受到合作网络中现实世界场景的启发。在每个时间步骤，新节点代表加入研究社区的新学生，大使节点代表新学生的导师，森林火灾般的过程代表研究人员相互合作的现实过程。
• 注释：Ko等人[74]还开发了HyperFF的简化和数学上可处理的版本，这导致了预期超边大小、超边数量和节点度的封闭形式方程。然而，简化版本在再现现实世界模式方面的能力较弱，特别是在缩小直径（见P26）方面。
• 讨论：HyperFF专注于以宏观方式保留现实世界超图模式。进一步考虑微观模式，如超边排序或重复，将是一个有趣的未来方向。
G9. THera。由Kim等人[71]提出的THera（传递性超图生成器）基于对现实世界超图传递性的观察（见P10）。
• 算法摘要：节点在具有多个级别的层次结构（具体来说，是树）中组织，其中节点被划分为不同级别的不相交级别，更深层次（即，更接近叶子）的级别包含更多节点，每个级别的节点被划分为不相交的组。组大小在不同级别上是相同的，因此更深层次有更多组。在生成超边时，THera有一定概率在组内本地生成，剩余概率在全球整个节点集中生成，较浅层级的节点更有可能被选择。
• 直觉：社区结构（见C12）自然赋予了高传递性（见P10）。层次结构允许不同层级的节点以不同的概率被选择，这意味着现实的偏斜度分布，特别是大量的小度节点和少量的大度节点（见P1）。
• 讨论：THera的超参数必须手动选择。最好有一个自动选择超参数的拟合算法。
G10. DARH。由Gallo等人[54]提出的DARH（离散自回归超图）基于现实世界超图中的时间局部性（见P16）。
• 算法摘要：在DARH中，每个时间步骤𝑡，对于每个潜在的超边𝑒：(1) 以某种概率𝑞，随机采样一个先前的时间步骤𝑡′ < 𝑡，并且𝑒在𝑡存在当且仅当𝑒在𝑡′存在；(2) 以剩余概率1−𝑞，我们进行另一次伯努利试验，成功概率为𝑦，并且𝑒存在当且仅当伯努利试验成功。𝑞和𝑦的值对于相同大小的超边是相同的，而对于不同大小的超边，值可以不同。
• 直觉：通过DARH从先前时间步骤复制状态的案例直接强加了时间依赖性（见P16）。相同大小的超边应该显示出类似的时间模式，因为它们有相同的参数𝑞和𝑦。
• 讨论：DARH模型能够根据超边大小的不同参数化来捕捉不同大小超边的时间模式变化（见P16）。
5.2 子超图生成器
现在，我们介绍子超图生成器。与全超图生成器不同，子超图生成器输出给定超图的一个子图，同时保留一些属性。
5.2.1 静态生成器。我们将在下面介绍静态子超图生成器。
G11. MiDaS。由Choe等人[32]提出的MiDaS（最小度偏差超边采样），旨在生成给定超边的代表性子超图，其中保留给定超图的属性（例如，P1, P4, P7, P8, 和 P14）。
• 算法摘要：在MiDaS中，超边是逐个采样的。每个超边的采样概率由其中的最小节点度决定。使用训练好的线性回归模型自动调整对高学位节点的偏差程度。
• 直觉：MiDaS通过引入对节点度的偏差来扩展随机超边采样。MiDaS的设计受到两个观察结果的启发：(1) 随机超边采样总体上工作良好，但未能生成具有高连通性（见B3）和足够高学位节点（见P1）的子超图，以及 (2) 保留度分布与保留其他几个超图属性密切相关。
• 注释：尽管MiDaS只直接考虑对节点度的偏差（见P1），但它保留了许多其他超图属性（例如，P4, P7, P8, 和 P14）。
• 讨论：研究保留节点度与其他超图属性保留之间强联系的更深层次原因将是有趣的。此外，考虑时间信息（如果可用）可能有益于性能。
G12. HRW。由Zhang等人[148]提出的HRW（混合随机游走），通过在超图上的随机游走进行采样。采样的（即，访问的）节点和超边用于估计输入超图的统计数据，如节点度和超边大小分布（见B4）。
• 算法摘要：HRW通过具有独立节点和超边转换的马尔可夫链蒙特卡洛（MCMC）获得节点和超边样本。基于采样的节点和超边估计输入超图的统计数据。
• 直觉：在超边上简单构建马尔可夫链具有高时间和空间复杂度。HRW将节点和超边转换分开，避免了考虑节点和超边的组合，从而降低了状态空间的复杂性。
• 注释：他们还提出了提高HRW采样效率和估计精度的技术。这些技术包括使用提升的马尔可夫链加快收敛的非回溯策略[27]和加快转换的跳过策略。
5.2.2 动态生成器。我们现在将介绍动态子超图生成器。
G13. TRHC。由Comrie和Kleinberg[37]提出的TRHC（时间重建爬山算法），主要基于对超图自我网络的观察（见P20, P21, 和 P22）。
• 算法摘要：给定一个自我网络，TRHC为给定自我网络中的超边分配时间顺序。从初始顺序开始，TRHC不断交换超边对以提高不同顺序的“适应度”，其中“适应度”由监督模型评估。当无法进一步改进时，过程终止。
• 直觉：监督模型被训练为应该给予与观察结果更匹配的时间顺序更高的“适应度”值。因此，提高“适应度”应该使时间顺序更接近观察到的模式。
• 讨论：这个生成器仅限于预测完全给定的一组超边的顺序，并且也仅限于超图自我网络。此外，在现实世界的场景中，一组超边的多个不同顺序可能同样可能且现实。
研究部分顺序（例如，因果关系[96]）可能是一个有趣的方向。
G14. CRU。由Benson等人[17]提出的CRU（相关重复并集），主要基于对现实世界时间超图时间行为的观察（见P16 和 P19）。
• 算法摘要：CRU以顺序方式生成子超图中的超边（例如，星形自我网络；见C5）。对于每个新的超边，其大小和其中从未出现过的新节点被认为是已知的。为了找到填充超边的其余节点，CRU从现有超边中采样一个超边，更近期的超边更有可能被选择。每个选定超边中的节点独立地以采样概率𝑝被复制到新的超边中，直到新超边填满。如果新超边未填满，则重复相同的过程。
• 直觉：从现有超边中采样建立了新超边和现有超边之间的时间相关性（见P16）。时间局部性的程度由对近期超边的偏差控制，相关程度（即，子集的重复）由采样概率𝑝决定。
• 讨论：所需的输入信息包括每个新超边的大小和其中的新节点数量，这可能过于强。保留所考虑的模式，即使使用较弱的预言者，也将是一个挑战性但有趣的未来方向。
6 未来应用和方向
在本节中，我们讨论超图挖掘的未来应用和方向，特别是超图模式。我们主要讨论与图挖掘相关的现有应用和研究主题，特别是我们在本调查中讨论的图模式的对应物。由于大多数超图模式是从图模式推广而来的，我们预计许多现有的图挖掘应用和方向将来也会被扩展和推广到超图。
为了进行更深入的讨论并获取更多参考文献，请参考补充文件[1]。
6.1 算法设计中的应用
首先，我们讨论超图挖掘在算法设计中的可能应用。图挖掘的许多结果，特别是模式，已经启发了为现实世界应用设计的创新图算法。我们期望这些应用可以推广到超图挖掘中。
度分布和奇异值分布。观察到现实世界中的图通常表现出重尾度分布，这已被用于图算法的设计，包括分布式图算法[119]、度分布估计算法[46]、图遍历算法[146]、知识图谱补全[125]和三角形计数算法[76]。类似地，现实世界图中的偏斜奇异值已被用于优化三角形计数[131]。在现实世界超图中也观察到了偏斜的度分布和奇异值分布（见P1和P14）。因此，上述应用可能可以扩展到超图，用于超图上的对应算法问题。
时间局部性。在许多现实世界的时间图中观察到时间局部性，其中在较小的时间窗口内出现的边更有可能进行交互。这一特性已被用于设计高效的三角形计数[80]和图遍历[75]算法。在超图中观察到了与时间局部性相关的几种模式（见P16和P20），我们期望这些模式在设计时间超图算法时有用。
直径。现实世界图中的小直径已在设计大规模图挖掘算法时被考虑[67]。因此，在现实世界超图中观察到的直径缩小（见P26）也可能对大规模超图挖掘有用。
核心-外围结构。一些算法利用现实世界图中的核心-外围结构进行有效的图压缩[90]和快速检索相似节点[64, 124]，因此我们期望超图中的这种结构（见P3）在相关任务[34]中也有用。
6.2 机器学习中的应用
除了算法设计，图模式也在机器学习中得到了广泛应用，特别是在图上的机器学习。这表明观察到的现实世界超图内的模式在超图相关应用中的潜在有用性，如下所述。
图神经网络和一般特征表示。图上的机器学习中最常见主题之一是特征表示，其中图神经网络（GNN）经常被使用。许多图属性和模式已被考虑用于增强GNN的性能，包括度分布[92]、同配性[128]、图模式[144]、自我网络[111]。结构模式也可以作为额外的节点特征，丰富用于图学习的特征[39]。最近，一系列研究专注于使用图模式对GNN进行理论分析。例如，图模式已被用于解释GNN的学习过程和产生的结果[112]，自我网络已被用于设计理论和实践上可转移的GNN模型[149]。此外，图模式，特别是图模式，可以用于节点级别和图级别的一般特征表示[101]。我们期望超图模式能够像它们的图对应物一样，在（超）图神经网络和超图的一般特征表示中发挥作用[11]。
链接预测和社区检测。链接预测和社区检测是图上的两个传统机器学习问题。许多图模式已在这两个问题中使用，包括同配性[36]、图模式[117]、自我网络的结构[129]和结构相似性（特别是邻域同质性）[28]。最近，超图的链接预测（即超边预测）[133]和社区检测[29]越来越受到关注，应用包括（1）识别一起购买的独特项目集，（2）为食谱提出新的配料组合，（3）建议研究人员之间的新合作，以及（4）揭示协作执行特定生物功能的基因簇。我们期待看到超图模式被用于这两个任务。
异常检测。异常检测是另一个传统的机器学习问题，基于图的异常检测[4]是一个流行的子主题。许多图模式已在基于图的异常检测中使用，包括图模式[109]、自我网络的结构[3]、𝑘-核心[123]和结构相似性（特别是邻域同质性）[25]。最近，超图的异常检测也已被研究[82]，Do和Shin[42]考虑了通过比较节点的超核心性和度的简单启发式异常检测方法。我们期待超图模式在这一应用中的更多使用。
推荐。推荐是机器学习中一个长期研究主题。图是构建推荐系统的重要工具，许多图模式，包括图模式[58]和自我网络的结构[47]，已在基于图的推荐模型中使用。超图也适用于此任务，特别是捆绑推荐[150]和群体推荐[6]，这些可以使用超图建模。我们期待超图模式在推荐系统中的更多应用。
6.3 对广义超图的分析和挖掘
在本调查中，我们主要讨论了简单的超图（即，无向和未加权的）。以下，我们想讨论几种类型的广义超图。
有向超图。有向超图是指每个超边内的节点被划分为源集和目标集的超图，它们在数学和理论计算机科学领域已被研究。有向超图也应用于许多任务，包括专家系统、图像分割、音乐创作、代谢网络分析、化学反应建模和对象检索。Ranshous等人[116]研究了现实世界有向交易超图中的模式，并应用观察到的模式进行交易分类。最近，Kim等人[72]将互惠概念扩展到有向超图，并研究了现实世界有向超图中的相关模式。我们期望在有向超图上探索更多模式。
加权超图。本调查中提到的大多数研究处理的都是未加权的现实世界超图，或者明确将数据集预处理为未加权的，尽管有些考虑了超边重复的情况[17, 84]。加权超图，特别是每个超边与数值相关联的超图，已被用于生物研究、图像检索和概念到文本的生成。最近，对边依赖的顶点权重（节点在不同超边中可以有不同的权重）的超图也引起了越来越多的兴趣[30]。我们期望在加权超图上探索更多模式。
异构超图。异构超图是另一种广义超图，其中节点可以属于不同的类别（或类型、标签等）。异构超图已被考虑用于理论研究和超图表示学习。在异构超图上还有更多模式等待发现。
不确定超图。广义超图还包括不确定超图，其中超边的存在或不存在不是确定性的，而是由概率或不确定性度量来控制。不确定性自然出现在现实世界场景中，当将现实世界系统建模为图或超图时考虑不确定性是很重要的[113]。我们期望在不确定超图上发现更多模式。
7 结论
超图是模拟现实世界中各种复杂群体交互的有价值的数学框架。超图的固有复杂性为超图挖掘带来了机遇和挑战，近年来越来越受到关注。
本调查彻底检查了迄今为止在超图挖掘中的进展，并为超图的模式、工具和生成器提供了全面的概述。我们还提出了完整的分类法，以提高对每个方面的结构化理解。最后，我们提出了几个研究方向。我们希望这个概述将为研究人员和实践者提供有价值的资源和见解，以推进超图在各个领域基础研究和实际应用的发展。
