超图挖掘综述：模式、工具与生成器|子结构|算法|超图挖掘

A Survey on Hypergraph Mining: Patterns, Tools, and Generators

超图挖掘综述：模式、工具与生成器

https://arxiv.org/pdf/2401.08878v2

超图属于高阶网络家族，是建模现实世界中群体交互的一种自然且强大的选择。例如，在建模可能不仅涉及两人，而是三人或更多人的协作网络时，使用超图使我们能够超越成对（二元）模式进行探索，并捕捉群体（多元）模式。超图的数学复杂性既为超图挖掘带来了机遇，也带来了挑战。超图挖掘的目标是发现不同领域真实世界超图中反复出现的结构性质，我们称之为模式。为了发现模式，我们需要工具。我们将超图挖掘工具分为三类：（1）零模型（用于检验观测模式的显著性）；（2）结构元素（即超图中的子结构，例如开三角与闭三角）；（3）结构量（即用于计算超图模式的数值工具，例如传递性）。此外，还存在超图生成器，其目标是生成能够忠实表征真实世界超图的合成超图。在本综述中，我们对超图挖掘的当前研究格局进行全面概述，涵盖模式、工具与生成器三个方面。我们为每一类内容提供了系统的分类体系，并就超图挖掘的未来研究方向进行了深入探讨。

CCS 概念：• 计算数学 → 超图；随机图；图算法；• 计算理论 → 图算法分析；• 信息系统 → 数据挖掘；• 以人为中心的计算 → 社交网络分析。

附加关键词与短语：超图挖掘，超图生成器，高阶网络

1 引言
群体交互在复杂的现实世界中普遍存在，并出现在多种情境下，包括科研协作 [16]、蛋白质相互作用 [53] 以及商品联合购买 [174] 等。这些涉及多个个体或实体的高阶交互，可以被自然且有效地建模为超图 [14, 160]。

超图是（成对）图的推广，由节点和超边组成。与图中只能连接两个节点的边不同，超边被定义为节点的非空子集，自然地建模了涉及任意数量节点的交互。超边大小的灵活性赋予了超图强大的表达能力，使其能够准确建模图所难以胜任的广泛群体交互。例如，在图1中，在合著超图中，每个节点代表一位研究者，每条超边代表一项合著关系，涉及构成该超边的各个节点所对应的研究者。需要注意的是，合著关系并不适合用图中的边来表示。当三位研究者合作发表一篇论文时，若连接所有可能的研究者配对，将无法区分这一群体交互与三篇由不同研究者配对合著的论文。超图这种固有的表达能力促使其在诸多领域得到应用，包括推荐系统 [170]、计算机视觉 [113]、自然语言处理 [43]、社交网络分析 [8]、金融分析 [176]、生物信息学 [53] 以及电路设计 [64]。

受使用（成对）图建模成功理解现实世界系统的启发（参见综述 [28]），近期研究深入探讨了建模这些系统的真实世界超图的结构。超图建模，尤其是每条超边大小的灵活性，引入了图论背景下未曾考虑的独特视角。这为超图挖掘带来了新的机遇与挑战：超图挖掘旨在通过发现并解释不同领域真实世界超图中反复出现的结构性质的成因，来增进我们对底层系统的理解。此类反复出现的结构性质通常被称为（结构）模式¹。因此，专门的挖掘工具（例如，用于定义结构模式的元素与量度）已被开发出来，以分析超图独特的结构特征。利用这些工具，研究者已揭示了真实世界超图中多种非平凡的局部结构模式 [16, 102, 118] 与全局结构模式 [45, 94]。这些模式中的大多数能够清晰地区分真实世界超图与随机超图，且通常伴随直观的解释或底层机制。它们显著增进了我们对现实世界系统的理解。

超图生成器（或超图生成模型）对于验证我们对结构性质的理解非常有用。通过复现观测到的模式，这些模型中的机制为真实世界模式提供了合理的解释。正因如此，结合超图结构模式的普遍性，超图生成器在近期研究中日益受到关注 [17, 45, 59, 101]。这些生成器能够成功生成合成超图，复现真实世界超图中观测到的特定模式，从而为理解与预测超图结构提供宝贵见解。此类合成超图对于模拟与评估超图算法也具有重要价值，尤其在收集或追踪真实世界超图不切实际的情境下。此外，这些生成器还可用于创建匿名化数据集（具体而言，即结构上与给定数据集相近的合成数据集），正如在图数据上已广泛开展的做法 [128]。

范围。在本综述中，我们深入探讨了关于真实世界超图挖掘的广泛研究，旨在对该领域的当前研究状态进行全面分析。我们的综述涵盖了超图挖掘的多个方面，包括结构模式（即在不同领域的真实世界超图中反复出现的结构性质）、挖掘工具（例如，用于定义模式的结构元素与结构量），以及能够复现并从而阐明模式的生成器。对于每种工具，我们阐释其背后的直观思想及其与先前概念的关联。我们为模式与生成器提供了系统的分类体系（即类别划分）。对于模式，我们首先依据是否考虑时间演化，将其划分为静态模式与动态模式。随后，我们根据每种模式所定义的最小单元，将模式进一步细分为不同层级：节点层级、超边层级、子超图层级与超图层级。对于生成器，我们依据其生成的是完整超图还是子超图，将其划分为全超图生成器与子超图生成器。随后，我们依据其生成的是静态超图还是动态（即时序）超图，将生成器进一步划分为静态生成器与动态生成器。我们基于生成器的输出、需求以及复现特定模式的能力，对其进行了系统比较。综上所述，本综述聚焦于真实世界超图中涌现的模式，以及旨在复现这些真实世界模式的生成器。有关本综述所涵盖研究工作的年份范围概览，请参见表1。

相关综述。真实世界图挖掘领域拥有丰富的历史背景，由此催生了大量模式与生成器的研究。Chakrabarti 与 Faloutsos [28] 对真实世界图中的模式及图生成器进行了全面概述。Drobyshevskiy 与 Turdakov [47] 以及 Bonifati 等人 [20] 则聚焦于图生成器，对其进行了详细分类。近年来，学界对超图的兴趣日益增长。Antelmi 等人 [7]、Gao 等人 [60] 以及 Zhang 等人 [181] 对超图学习进行了系统性综述。Kim 等人 [90] 专门对超图神经网络进行了深入综述。Preti 等人 [139] 总结了高阶网络（包括超图）的高级分析技术。部分综述聚焦于超图的应用，包括可视化 [56] 与划分 [25]。Torres 等人 [160] 广泛探讨了包括超图在内的不同数学框架，以表征高阶复杂系统。类似地，Battiston 等人 [14] 从动力系统与随机过程的视角，考察了超图作为建模高阶交互工具的有效性。此外，已有多个为超图分析构建的开源库 [6, 76, 116]。在本综述中，我们系统性地考察真实世界超图中的结构模式，以统一的超图模式分类体系呈现超图挖掘的最新进展，并探讨其在超图生成及其他下游任务中的实际应用。有关本综述结构的可视化图示，请参见图2。

2 预备知识

虽然星扩展包含了超图中所有的关联信息，但节点和超边都被统一表示为节点。然而，由于节点和超边具有截然不同的特征 [173]，这种对称处理可能并不理想。在大多数超图操作、结构元素和数量计算中，节点和超边是被区别对待的，从而打破了这种对称性，而这在星扩展中是无法实现的。参见图 3 以获取上述两种二元投影的示例。

B8. 时序超图。与上文介绍的静态超图相比，时序超图（temporal hypergraphs，也称为动态超图 dynamic hypergraphs）不仅描述了超图的结构信息，还描述了其时间演化。

3 工具

在本节中，我们介绍用于超图结构模式的挖掘工具。³ 通常，工具包括任何可用于定义或挖掘超图结构模式的事物。典型的工具包括零模型、结构元素和结构量。在图 5 中，我们为下文将要介绍的工具提供了一个概览分类体系。

3.1 零模型

我们首先介绍零模型（null models）。零模型的概念对于显著性检验 [141] 非常重要，在显著性检验中，人们通常证明观测到的现象在零模型中几乎不可能发生，从而表明观测到的现象是显著的、非平凡的或令人惊讶的。对于成对图，许多随机图模型已被用作零模型，包括 Erdős-Rényi 模型 [49] 和 Chung-Lu 模型 [38]。零模型是超图生成模型，通常 (1) 依赖于基本信息（例如，节点度和边大小），并且 (2) 缺乏超出给定信息来复现真实模式的设计或机制。因此，它们很容易无法以全面的方式捕捉真实世界超图的性质。相比之下，第 5 节中作为“生成器”讨论的超图生成模型旨在有效地复现真实的结构模式。此外，零模型和生成器服务于不同的目的。零模型主要用于与真实超图进行比较，例如在假设检验中或验证在真实世界超图中观测到的模式的显著性。相比之下，生成器旨在复现真实世界超图中观测到的真实模式，有助于解释和理解产生这些模式的底层机制。

N1. 配置模型 (Configuration model)。配置模型旨在生成保留节点度分布和超边大小分布的随机超图 [33]。这与成对图（pairwise graphs）的配置模型不同，后者仅保留度分布。请注意，存在更先进的超图生成器，可被视为广义配置模型。我们将在第 5 节介绍它们。在实践中，人们可以使用存根匹配（stub matching），这种方法速度快，但可能会产生包含重复节点的超边；或者使用成对重排（pairwise reshuffling），这种方法避免了包含重复节点的超边，但速度较慢 [33]。

N2. 随机填充模型 (Random filling model)。随机填充模型是配置模型（见 N1）的一个简单变体，它保留超边大小分布，但不保留节点度分布。具体而言，给定一个超图，它生成的超边大小要么精确遵循原始超边大小分布（要么是根据该分布进行采样）。对于每条超边，其组成节点是从所有节点中均匀随机采样的。

3.2 结构元素

结构元素包括子结构（例如，子超图；见定义 2.1），以及它们之间的关系和相互作用。这些元素有助于我们揭示超图的底层结构，并且通常是定义结构模式所依据的对象。

E1. 开三角与闭三角。三角形（即三节点团）是成对图（pairwise graphs）中的重要基元，因为它们被用于衡量各种结构性质，如社区结构 [157] 和传递性 [77]。在超图的语境下，三角形可以分为开三角（open）和闭三角（closed），它们描述了三个节点之间不同种类的高阶交互 [16]。如图 6(b) 所示，在开三角中，每对节点都在一个或多个超边中共现，但这三个节点不共享任何超边。相反，在闭三角中，所有三个节点共同出现在至少一条超边中。值得注意的是，这一概念也可以扩展到高阶。⁴ 例如，考虑图 6 中展示的超图。在这个超图中，节点 2、3 和 5 形成一个开三角，而节点 3、5 和 8 形成一个闭三角。重要的是，闭三角（要求至少有一条包含三个节点的超边）无法在成对图中定义，它们捕捉了超图独有的高阶局部结构。

E4. 时序超图模体（TH-motifs）。为了描述三条相连时序超边的时间动态，除了重叠模式外，还定义了 96 种时序超图模体（TH-motifs）[103, 104]。从结构角度来看，TH-motifs 遵循 H-motifs（见 E3）的概念，通过考虑 H-motifs 中使用的相同七个子集的空性。在时间方面，TH-motifs 是为在短时间间隔内出现的三条时序超边定义的，并考虑了时间局部性（temporal locality）。此外，TH-motifs 的定义纳入了这三条时序超边的相对到达顺序，这使得能够进一步刻画那些在静态 H-motifs 中无法区分的模式。

E5. 自我网络（Ego-networks）。以单个节点为中心的交互通常通过构建自我网络（ego-network）[124] 来分析，其中中心节点被称为自我节点（ego-node，或简称 ego）。自我网络对其自我节点 u 与 u 的邻居（称为alter-nodes，或简称 alters）之间的交互进行建模。Comrie 和 Kleinberg [40] 通过考虑不同范围的交互，定义了三种类型的自我网络（星型自我网络、辐射型自我网络和收缩型自我网络）。

E10. 超图社区（Hypergraph communities）。社区的概念（即内部连接紧密且与外部节点连接相对稀疏的节点组）已在成对图上得到广泛研究 [57]。该概念已被扩展至超图 [2, 146, 179]。在超图中，社区是指这样的节点组：与属于不同社区的节点相比，同一社区内的节点更有可能共同形成超边。聚类（Clustering）是将节点分组为社区的过程，已有许多算法被提出用于发现超图中的社区 [54, 80, 110]。

E11. 其他稠密子结构（Other dense substructures）。人们提出了超图中重要群体的各种定义，其中一个常见的类别是基于稠密子结构来定义重要群体。基于节点子集具有高平均度（即高密度；见 Q10）的条件，人们提出了“稠密子超图”的各种定义 [18, 72, 74, 96]。例如，Musciotto 等人 [129] 提出根据节点交互的一致性程度来定义稠密子结构。最近，Veldt 等人 [165] 提出考虑具有不同 p 值的度序列的 p -范数，从而允许灵活地强调节点度，并将这一思想应用于定义广义稠密子图。这一思想也可以推广用于定义稠密子超图。

3.3 结构量

结构量（Structural quantities）是用于定义进而挖掘超图模式的数值工具。通常，我们针对特定的结构量，将真实世界超图与由零模型生成的随机超图进行比较，并展示显著的数值差异。

Q3. 距离（Distances）。基于局部连通性信息（例如，游走和路径；见 B3），人们提出了超边中的各种距离度量。Vasilyeva 等人 [163] 以及 Li 和 Fadlallah [109] 提出了基于超图上随机游走的距离度量。Aksoy 等人 [4] 提出了一种考虑超图中高阶连通性的距离度量，Preti 等人 [138] 为该度量提出了一种快速近似算法。这些距离度量已被用于定义节点和边的中心性分数 [51, 177]，并应用于真实任务，如关键基因识别 [53]。

Q4. 中心性分数（Centrality scores）。人们提出了各种分数来衡量超图中节点和边的结构中心性。除了基于距离的分数（见 Q3），还有几种基于邻接/关联/拉普拉斯矩阵（见 B2 和 B7）的特征值或特征向量的谱中心性分数（spectral centrality scores）被提出 [15, 95, 161]。Xie 等人 [171] 利用引力模型引入了节点中心性，而 Hu 等人 [71] 基于冯·诺依曼熵（von Neumann entropy）定义了中心性。

Q7. 同配性（Assortativity）。同配性的概念量化了成对图中相似节点相邻的倾向 [133]。高同配性值表明，与不相似的节点相比，相似节点更有可能相邻。相似性（similarity）通常是相对于节点度来定义的，即，如果节点具有相似的度，则被视为相似。Landry 和 Restrepo [97] 通过捕捉超边内节点间的度相关性如何偏离随机情况下的预期，将同配性的概念扩展到了超图。

Q8. 单纯性（Simpliciality）。由于超边大小的灵活性，一条超边可以封装其他超边（见 E8）。超图单纯性（simpliciality）通过评估大超边包含所有可能的较小子集的程度，量化了这种层次结构在超图中展现得如何。具体而言，超图的单纯性是包含所有潜在子集的极大超边数量与超边总数的比率 [98]。较高的比率表明超图由许多完全封装了所有较小交互的超边组成，反映了强烈的包含结构。

Q9. 特征剖面（CPs）。为了更好地分析给定超图的结构性质，我们可以同时考察多个感兴趣的结构模式（例如，H-motifs）来构建该超图的特征剖面（CP）。为此，第一步是获取每个模式的数值频率，例如，对于 H-motifs，我们可以简单地计数它们的实例。然后，对于每个模式，通过将其在给定超图中的频率与在随机超图中的频率进行比较，我们可以确定其统计显著性。最后，CP [102, 125] 是一个向量，它总结了整个超图关于各种模式的结构模式，允许在不同规模的可能变化的超图之间进行有意义的比较。

Q14. 模块度（Modularity）。为了评估成对图中的社区结构强度（见 E10），Newman [132] 引入了模块度（modularity）的概念。高模块度值意味着与属于不同社区的节点对相比，每个社区内的节点对之间更有可能存在边，因此它意味着强烈的社区结构 [19]。模块度的概念已通过多种方式扩展到了超图 [62, 80, 131, 175]。模块度测量了给定超图中的社区结构强度与参考随机超图之间的差异。值得注意的是，Chodrow [33] 考虑了具有各种参考随机超图定义的广义模块度。

4 结构模式

在本节中，我们介绍真实世界超图中的结构模式（有关真实世界中公开可用且常用的超图数据集列表，请参阅补充文档 [1] 的表 1）。结构模式是指在不同领域的真实世界超图（及其所建模的真实世界系统）中反复出现的结构特征 [28]。我们将结构模式分类如下：

静态模式与动态模式。静态模式描述了静态超图或时序超图（见 B8）单个快照的特征，而动态模式描述了时序超图随时间的演化。与关注结构行为的静态模式相比，动态模式提供了关于时间行为的额外见解，例如群体交互的形成与持续性。
节点级、超边级、子超图级与超图级模式。模式的级别取决于用于定义该模式的基本元素。如果一个模式描述了单个节点（或超边）的某些性质，则将其归类为节点级（相应地，超边级）模式。描述整个超图性质的模式被称为超图级模式。定义在节点和/或超边的特定组合上的模式被归类为子超图级模式。

这两种分类形式是正交的，通过它们的组合总共形成了八个子类别。在图 9 中，我们提供了下文将要介绍的结构模式分类体系的概览。本节侧重于描述观察到的模式，而不深入探讨其背后的具体原因。在第 5 节中，我们要通过简单的机制复现这些模式，旨在揭示潜在的解释。

4.1 静态模式

我们首先介绍静态模式。这些模式描述了节点和超边的结构性质，以及真实世界超图的整体特征。静态模式不包括那些与时间变化相关的模式。

4.1.1 节点级模式。我们将调查与单个节点性质相关的静态模式，节点是超图中的基本元素。

P1. 重尾度分布。真实世界超图的度分布（见 B4）通常表现出重尾分布 [94]，大多是幂律分布（见 B5）。这表明少数节点参与了异常多的群体交互，而大多数节点仅参与少量交互。在成对图上也观察到了类似模式，⁶ 它们部分由“富者愈富”[52] 解释，这暗示了一个时间过程，其中度数较高的节点随着时间的推移更有可能更快地增加其度数。少数高度数节点被称为枢纽（hubs）[13]，它们在许多应用中发挥着重要作用。

P2. 重尾超核度分布。对于节点，其度可以被视为一种中心性度量，其超核度（见 Q2）也是如此。Bu 等人 [22] 观察到，在真实世界超图中，节点的超核度通常表现出重尾分布（见 B5）。这意味着存在涉及少数节点的高度稠密子超图，而大多数节点不属于此类子超图。核度（Coreness）是超核度在成对图中的对应概念，也已知在真实世界图中通常表现出重尾分布 [155]。对于许多中心性分数（见 Q4），虽然未明确讨论重尾分布，但通常存在中心性值显著高于其他节点的节点 [15, 71, 171]。

P3. 核心 - 边缘结构。许多真实世界超图具有核心 - 边缘结构，其中我们有核心节点和边缘节点。大量超边应在核心节点之间形成，而边缘节点彼此之间连接不佳（即，不在许多超边中共存），并且应主要存在于至少有一个核心节点存在的超边中 [5, 136, 162]。成对图中的类似结构也已被研究 [21]。

4.1.2 超边级模式。我们现在将调查超边级静态模式。就像节点一样，超边也是超图中的基本结构元素（见 B1）。因此，检查超边级模式使能够从不同角度洞察真实世界超图的结构特征。

P4. 重尾大小分布。成对图与超图之间的一个根本区别在于，超边具有可变的大小，连接任意数量的节点，而成对图中的边只能连接两个节点。因此，超边的一个关键性质是其大小，即在一条超边中共现的节点数量。真实世界超图中超边大小的分布往往遵循重尾分布 [94]（见 B5）。这意味着存在大量小尺寸超边，而极大超边也往往存在。

P5. 高同质性。超边的同质性（见 Q5）衡量超边中的节点在结构上的相似程度。Lee 等人 [101] 观察到，真实世界超图中的超边往往比通过 HyperCL 模型（见 E3）获得的随机超图中的超边具有显著更高的同质性。这一模式意味着真实世界超边更有可能由结构相似的节点填充，而不是随机选择的节点。

P6. 实质性封装。LaRock 和 Lambiotte [99] 通过与随机超图比较，研究了真实世界超图中的封装（见 E8），其中相同大小的超边被分组在一起，并且每个超边组内的节点标签被随机排列。这保持了相同大小超边之间的重叠模式，同时随机化了不同大小超边之间的重叠模式。他们观察到，与相应随机超图中的超边相比，真实世界超图中的超边往往表现出显著更高程度的封装（即，封装更频繁地发生）。这一模式突出了真实世界超图中超边之间高互连性的一个方面。

4.1.3 子超图级模式我们现在将调查子超图级静态模式。子超图级模式是指那些既不涉及单个节点/超边，也不涉及整个超图的模式。相反，它们是定义在节点和/或超边的组合上的，例如，节点的子集和超边对。

P7. 重尾群组度分布。我们已经看到真实世界超图中存在（单个）节点度的重尾分布（见 P1）。现在我们深入探讨真实世界超图中节点群组的度分布（见 Q1）。群组度的分布已被几位研究人员研究过：

P8. 重尾交集大小分布。我们已经看到真实世界超图中（单个）超边大小遵循重尾分布（见 P4）。我们现在将范围扩展到超边对并研究超边交集。研究超边交集使我们能够从不同角度研究超图的连通性。Kook 等人 [94] 观察到，真实世界超图中超边对的交集大小分布遵循重尾分布。此外，他们还观察到真实世界超图中的一些超边对共享大量公共节点（即，大交集），这在由随机填充模型（见 N2）生成的随机超图中是无法观察到的。

P9. 实质性的高阶连通性。Kim 和 Goh [87] 从另一个角度研究了超边交集。他们提出构建图来描述具有不同阈值 m 的超图的高阶连通性（见 E7），其中每条超边在构建的图中表示为一个节点，如果两条对应的超边共享至少 m 个公共节点，则构建图中的两个节点相邻。他们观察到，真实世界超图倾向于在较高的 m 值下保持大的连通分量，而在通过配置模型（见 E1）获得的随机超图中则不然，这表明真实世界超图中存在实质性的超边交集，这与上述观察（见 P8）一致。

P10. 高传递性。几位研究人员研究并扩展了超图中的传递性（见 Q6），从不同角度观察到真实世界超图中的高传递性：

这些模式通常意味着，如果（群组）节点共享公共邻居，它们更有可能在超边中共同出现。

P11. 密集重叠的自我网络。超图的密度（见 Q10）或重叠度（见 Q11）衡量了其超边相互重叠的程度。Lee 等人 [101] 观察到，在星型自我网络（见 E5）中，真实世界超图中星型自我网络的密度和重叠度显著大于通过 HYPERCL 模型（见 E3）获得的随机超图中的密度和重叠度。这意味着真实世界超图中的超边比随机对应物中的超边具有更多的局部重叠，这也与高传递性相关（见 P10）。

P12. 社区结构。社区（见 E10）在真实世界超图中普遍存在，这通过使用扩展的（归一化）割（见 Q12）[67, 110, 164, 166]、电导（见 Q13）[68, 159, 164] 和模块度（见 Q14）[62] 量化的强社区结构得以证明。Contisciani 等人 [41] 观察到真实世界超图中重叠社区的普遍性，并提出了一种统计方法来检测此类社区。Lotito 等人 [119] 进一步观察到真实世界超图中的层次化（即社区被进一步划分为更小的社区）和多尺度（即社区存在于各种尺度上）社区结构。值得注意的是，Torres 等人 [160] 指出，相同原始数据的不同超图表示可能会展示不同的社区结构。

P13. 稠密子超图。真实世界超图通常表现出稠密子结构（见 E11），其特征为高密度（见 Q10）或高重叠度（见 Q11）。它们的存在与同一组（或相似）节点在多个超边中重复共现有关 [17, 101]。一些研究表明，与随机超图相比，真实世界超图倾向于表现出更稠密的子超图 [33, 101]。

P14. 模式的强表征能力。几种度量与模式可以作为超图的有效表征工具。具体而言，真实世界超图来自不同的领域（或字段），并且通常观察到同一领域内的超图在某些度量和模式方面是相似的，而不同领域中的超图则相对不相似。

Benson 等人 [16] 使用开三角和闭三角（见 E1）的计数来表征真实世界超图。具体而言，开三角数量与闭三角数量的比率是区分不同领域超图的有用度量。
Lotito 等人 [118] 使用高阶网络模态（HO-motifs；见 E2）的频率来表征真实世界超图。具体而言，同一领域内的超图表现出相似的 HO-motifs 归一化计数分布，而来自不同领域的超图则表现出显著差异。Juul 等人 [79] 观察到关于 m -模式（见 E2）分布的类似现象。
Lee 等人 [102] 使用 H-模体（见 E3）构建真实世界超图的特征剖面（CPs；见 Q9）。此类 CPs 基于 H-模体总结局部结构模式，并且基于 CPs 可以清晰地区分来自不同领域的真实世界超图。
LaRock 和 Lambiotte [99] 观察到，来自同一领域的超图表现出相似的与封装相关的模式（例如，封装程度如何随超边大小变化），而此类模式在不同领域中则有所不同。此外，Landry 等人 [98] 观察到，同一领域内的超图表现出相似水平的单纯性（见 Q8），而来自不同领域的超图则显示不同水平的单纯性。

结构模式的强大表征能力进一步验证了它们作为分析真实世界超图工具的有用性和意义。此外，结构模式还可用作结构特征 [16, 102–105]，用于具有各种下游应用的机器学习（见第 6.2 节）。

4.1.4 超图级模式。我们现在将调查超图级静态模式。超图级模式涉及超图作为整体的性质，检查它们使我们对真实世界超图获得宏观见解。

P15. 偏斜奇异值分布。真实世界超图的不同矩阵表示的奇异值分解（SVD）可以提供关于超图结构性质的重要见解。具体而言，检查奇异值分布的偏斜性可以提供关于超图内底层层次结构和社区结构（见 P12）的信息，正如研究人员对成对图所做的那样 [46, 85, 150]。

对于真实世界超图的关联矩阵（见 B2），已观察到偏斜奇异值分布（即，当我们按降序排列奇异值时，值显著下降）[94]。
Do 等人 [45] 考虑了一种使用多级分解（见 E6）的不同矩阵表示方式，并观察到真实世界超图的每个 k 层分解图的邻接矩阵的奇异值是偏斜的。

奇异值的大小反映了对应节点（对于关联矩阵）或节点组（对于多级分解图的邻接矩阵）的结构重要性（例如，影响力）。因此，上述观察表明，真实世界超图中的一些节点或节点组比其他节点或节点组普遍得多且更具影响力。

4.2 动态模式

我们现在介绍动态模式（dynamic patterns）。给定时序超图，动态模式描述了超图内部及超图本身的时间演化或变化。

4.2.1 超边级模式。我们现在将调查超边级动态模式（hyperedge-level dynamic patterns），描述超边出现之间的时间关系。

P16. 频繁的超边重复。过去事件的重演在各种系统中很普遍。超边重复（Hyperedge repetition），即过去超边的重演，也在真实世界超图的演化中被观察到。

Benson 等人 [17] 观察到，许多超边在真实世界时序超图的演化过程中重复出现。
Lee 和 Shin [103, 104] 进一步观察到，真实世界时序超图中超边重复次数的分布通常遵循重尾分布。
Lee 和 Shin [103, 104] 还观察到，与随机超图相比，超边重复在真实世界超图中发生得更频繁（即，同一条超边两次出现之间的时间间隔更短）。随机超图是使用 HYPERCL（见 N3）生成的，且超边的时间戳是从原始时间戳随机重排的。
Cencetti 等人 [27] 使用了突发行为（bursty behaviors，即同一条超边在短时间间隔内重复多次）的概念，并观察到突发行为在真实世界超图中比在通过随机打乱相同大小的时序超边时间戳获得的随机超图中更为普遍。

上述工作的作者普遍观察到，与随机对应物相比，超边重复在真实世界超图中更为常见，尤其是对于大超边。

P17. 时间局部性。在成对图演化中，时间局部性（temporal locality）指的是新交互更类似于近期交互而非较早交互的倾向 [100, 122]。对真实世界超图中超边的结构相似性与其出现时间之间关系的考察也揭示了时间局部性的存在。

除了整个超边的重复行为（见 P16），关于超边内子集重复的时间局部性，为时序超图演化提供了独特的见解。

P18. 时间强化。随着时序超图的演化，新超边的组成受到先前超边的影响。时间强化（temporal reinforcement）现象描述了先前超边如何影响新超边的组成。具体而言，Cencetti 等人 [27] 观察到，如果一组节点在过去曾在多条超边中共同出现，那么同一组节点在未来更有可能继续在某些超边中共同出现，并且随着过去共现期长度的增加，这种可能性也会增加。这种模式使我们能够分析群体交互的时间稳定性。

4.2.2 子超图级模式。我们现在将调查子超图级动态模式。此类模式描述了节点和/或超边组合的时间行为。

P19. 幂律持续性。在真实世界时序超图中，同一组节点可能会随时间推移在多个超边中共同出现。一组节点的持续性（persistence）量化了它们随时间共同出现的一致性（见 Q15）。Choo 和 Shin [37] 观察到，在真实世界时序超图中，持续性（具体而言，即持续性值与具有该持续性值的节点组数量之间的关系）通常遵循幂律分布。该模式意味着总体而言，大多数节点组具有较低的持续性值，但也存在少数持续性异常高的节点组。这种模式与上述超边级模式（见 P16-P18）相关。然而，通过考虑超边内的组成节点组而非整个超边，它提供了一个独特的视角。

P20. 单纯闭包。单纯闭包（simplicial closure）的概念将成对图中的三元闭包（triadic closure）[156] 概念扩展到了超图，暗示了闭三角（或其高阶对应物）形成的可能机制（见 E1）。Benson 等人 [16] 考察了真实世界超图中三个节点之间闭三角的出现（即单纯闭包事件的发生）与其在团扩展（见 B6）中的成对连接之间的关系。值得注意的是，他们通过计算团扩展中的边重复次数考虑了边权重，即他们计算了每对节点共同出现的超边数量。他们观察到了单纯闭包的存在，即，随着团扩展中考虑节点之间的连接数量和/或权重的增加，单纯闭包事件的可能性趋于增加。这种模式可以很容易地用于超边预测 [16]，扩展了三元闭包在链路预测 [73] 中的效用。

P21. 自我网络中的时间局部性。识别真实世界超图中自我网络（见 E5）的时间增长模式，是理解和预测围绕单个节点的群体交互动态的重要一步。正如单个超边的演化表现出时间局部性（见 P17）一样，自我网络的演化也表现出时间局部性。

Comrie 和 Kleinberg [40] 观察到，在自我网络内部，时间戳更接近的超边也倾向于表现出结构相似性，即共享大量节点。具体而言，他们通过自我网络中时间连续边的平均交集大小（见 Q16）来衡量结构相似性。此外，他们观察到随着自我网络随时间演化和增长，这种结构相似性会降低。
他们还从 alter 网络（见 E5）的角度探索了时间局部性，并观察到 alter 网络内两条连续超边之间的平均时间间隔短于通过随机打乱超边顺序获得的随机超图中的时间间隔。

与整个超图中超边的时间局部性（P17）相比，自我网络内的时间局部性为局部超图演化提供了独特的见解。

P22. 自我网络的人择原理。回想一下，辐射型和收缩型自我网络可能包含仅由不包含自我节点的 alter 节点组成的超边（见 E5）。因此，此类自我网络的形成甚至可能在自我节点介入之前就已经开始。Comrie 和 Kleinberg [40] 探索了自我节点进入其自身自我网络的时间点。

在收缩型自我网络中，我们经常观察到自我节点的到达时间与自我网络的大小之间存在近乎完美的正相关关系。具体而言，如果自我网络较大，自我节点更有可能较晚到达。此外，与通过随机打乱超边顺序获得的随机网络相比，自我节点倾向于在真实世界的收缩型自我网络中较晚到达。
在辐射型自我网络中经常注意到一种类似但相对较弱的趋势。在辐射型自我网络中，即使它们具有相当大的规模，自我节点通常在引入第五条超边之前出现。此外，正如在收缩型自我网络中一样，与通过随机打乱超边顺序获得的随机网络相比，自我节点倾向于在真实世界的辐射型自我网络中较晚到达。

这些模式为自我网络构建的底层机制提供了见解，被称为自我网络的人择原理（anthropic principles），这类似于人类研究史前历史的方式。

P23. 自我网络的新颖率模式。自我网络中新添加的超边可能包含新颖节点（novel nodes），即此前未在自我网络中出现过的节点。此类新颖节点的数量被称为新颖率（novelty rate）。Comrie 和 Kleinberg [40] 调查了新颖率如何随自我网络演化而变化。

在星型和辐射型自我网络中，平均新颖率逐渐下降直到某一点。过了那一点后，新颖率保持几乎恒定（对于辐射型自我网络）甚至显示出增加趋势（对于星型自我网络）。
在收缩型自我网络中，平均新颖率随时间持续下降。

此类新颖节点总体上难以预测，且与许多实际问题相关，例如冷启动 [151]。理解此类节点出现背后的机制在理论和实践上均具有重要意义。

P24. TH-模体的强表征能力。时序超图模体（TH-motifs；见 E4）是静态超图中定义的超图模体（H-motifs）概念的时间扩展。从给定时序超图中每种 TH-模体（共 96 种）的实例计数中，时序超图的结构和时间模式可以总结为一个 96 维向量，称为关于该超图 TH-模体的特征剖面（CP；见 Q9）。利用 CPs，可以有效地区分来自不同领域的时序超图，而且这种区分比仅使用静态信息通过 H-模体实现的区分更为清晰 [103, 104]。这证明了 TH-模体通过捕捉时间和结构模式来表征时序超图的有效性。

4.2.3 超图级模式。我们现在将调查超图级动态模式。这些模式描述了超图作为整体的特征随时间如何变化。

P25. 重叠减少。Kook 等人 [94] 调查了真实世界时序超图中超边的结构互连性随时间如何演化。具体而言，他们观察到所有超边对中相交超边对的比例随时间趋于减少。这一观察结果与以下发现一致：随着超边出现之间的时间间隔增加，超边之间的相似性会减弱（见 P17）。

P27. 直径收缩。直径收缩（Shrinking diameter）是在真实世界成对图中观察到的另一种模式 [108]，其中有效直径（见 Q17）通常随着图的增长而减小。这种趋势可以自然地扩展到超图，Kook 等人 [94] 确实在真实世界超图的演化中观察到了这种趋势。这表明随着真实世界超图规模的扩大，信息或影响力可能会传播得更快。

5 生成器

在本节中，我们介绍超图生成器。我们重点关注基于真实世界超图性质的生成器。超图生成器在大规模建模中起着至关重要的作用，它们通过生成模仿真实世界超图结构的合成数据集，促进了基准测试和可扩展性测试。在图 10 中，我们为下文将要讨论的生成器提供了分类体系。我们将感兴趣的生成器分类如下：

全超图和子超图生成器。全超图生成器生成完整的超图，而子超图生成器生成超图的部分。
静态和动态生成器。静态生成器生成静态超图，而动态生成器生成动态图（即时序超图；见 B8）。值得注意的是，在某些工作中，作者并未明确说明所提出的生成器是生成静态超图还是动态超图。对于此类情况，我们根据生成过程是否可以被解释为具有时间依赖性的演化过程来对生成器进行分类。例如，基于优先依附（preferential attachment）的生成器可以自然地被解释为演化过程，而使用节点打乱或重连的生成器则不能。

这两种分类是正交的，因此我们总共有四个子类别。对于每个生成器，我们提供其算法过程的摘要以及直观理解和讨论（如有）。有关每个生成器的详细输入和输出，请参见表 2。

5.1 全超图生成器

我们首先介绍全超图生成器。全超图生成器以一些超图统计量作为输入（通常带有一些额外的模型特定超参数），并输出一个完整的超图，该超图旨在保留真实世界超图中的一些结构模式。

5.1.1 静态生成器。我们将在下面介绍静态全超图生成器。

G1. HYPERLAP。HYPERLAP 由 Lee 等人 [101] 提出，基于真实世界超图中超边的重叠模式（见 P5 和 P11）。它可以看作是 HYPERCL（见 N3）的多级扩展，其中该扩展有助于复现重叠模式。

算法摘要：节点被组织在多个层级中，其中每个层级包含所有节点，但粒度不同。具体而言，从上到下，某一层级的每个群组在下一层级被划分为两个群组，因此更深（即更接近底部）的层级包含更多的群组。在生成每条超边时，HYPERLAP 首先采样一个层级，然后在该层级中选择一个群组。所选群组中的节点被采样以填充该超边，采样的概率与度成正比。
直观理解：由于超边是基于群组生成的，同一群组内的节点在结构上是相似的，这使得生成的超边具有高同质性（见 P5）。由于每个自我网络倾向于包含结构相似的节点，这些节点在许多超边中共同出现，因此每个自我网络的密度（见 Q10）和重叠度（见 Q11）自然产生（见 P11）。最后，位于深层（即接近底部）小群组中的节点对或节点三元组也属于所有较浅层（即接近顶部）层级的同一群组，因此它们被更频繁地选择共同形成超边。因此，更多的超边包含并在这些节点对或节点三元组处重叠，这意味着节点对和节点三元组的度分布呈现偏斜的重尾分布（见 P7）。
Lee 等人 [101] 还提出了 HYPERLAP+，其在 HYPERLAP 的基础上额外包含了一个自动超参数选择方案。

G2. CIGAM。CIGAM（continuous influencer-guided attachment model，连续影响者引导依附模型），由 Papachristou 和 Kleinberg [136] 提出，旨在捕捉真实世界超图中的核心 - 边缘结构（见 P3）。

算法摘要：每个节点被分配一个声望值（prestige value），并且每条潜在的超边被独立生成，其中采样概率由组成节点的声望值决定。
直观理解：具有高声望值的节点被视为“核心节点”。每条生成的超边很可能包含核心节点，这意味着一种核心 - 边缘结构（见 P3）。为了降低似然估计中的计算复杂度，仅考虑每条潜在超边中的最大声望值。
为节点分配声望值的想法可以与其他超图生成器结合，以捕捉更多性质，例如模体（见 E2 和 E3）。

G3. HYPER-dK。由 Nakajima 等人 [130] 提出的 HYPER-dK 系列是一族超图参考模型，它扩展了成对图的 dK 系列 [121]。它们生成保留节点和超边给定局部性质（例如，P1 和 P7）的超图。

G5. HSBM。HSBM（hypergraph stochastic block model，超图随机块模型），由 Ghoshdastidar 和 Dukkipati [61] 提出，可以生成社区结构（见 E10 和 P12），并且对于社区发现很有用。

算法摘要：节点被划分为多个群组（即社区），并且边根据作为节点成员组合函数的概率生成。
直观理解：社区结构的强度可以通过该函数直接调整。例如，我们可以通过增加同一群组内节点的边概率来生成具有强社区结构的超图。
更广义的模型，例如超图审查块模型（hypergraph censored block model）[2]、子超图随机块模型 [112]、超图度校正随机块模型（hypergraph degree-corrected stochastic block model）[34] 以及超图同步生成器（hypergraph simultaneous generators）[137]，也已被考虑。

5.1.2 动态生成器。我们现在将介绍动态全超图生成器。

G8. HYPERPA。HYPERPA 由 Do 等人 [45] 提出，基于关于 k k 层分解图（见 P7、P10 和 P15）的观察。它是优先依附（preferential attachment）[12] 的群组级扩展，其核心思想是新节点更有可能依附于现有的高度数节点，使得“富”节点更“富”。例如，合著过许多论文的研究人员很可能拥有共同的兴趣，这将导致未来更多的合作。

算法摘要：对于每个节点 v v，HYPERPA 首先采样“新”超边的数量。对于每条“新”超边，HYPERPA 采样一个超边大小 s s，然后使用优先依附以与群组度（见 Q1）成正比的概率将节点 v v 依附到一个大小为 ( s − 1 ) 的群组上。
直观理解：众所周知，优先依附能够产生具有偏斜度分布（见 P1）、高聚类系数、小直径等特征的图。直观地看，HYPERPA 也产生具有推广到超图的类似模式的超图（见 P7、P10 和 P15）。值得注意的是，HYPERPA 中的优先依附是以群组方式进行的，这产生了偏斜的群组（以及单个）度（见 P1 和 P7）。
HYPERPA 以动态方式生成超边。然而，超边的时间戳在观察和评估中均未考虑。将观察和评估扩展到时序超图将是一个有趣的未来方向。有关超图中优先依附的更一般讨论，请参阅 [144]。

G9. HMPA。HMPA（high-modularity preferential attachment，高模块度优先依附），由 Giroire 等人 [62] 提出，也使用了优先依附的思想。该生成器还考虑了具有高模块度（见 Q14）的社区结构（见 P12），这是在真实世界超图中观察到的。

算法摘要：节点被显式划分为社区（见 E10）。在每个时间步，要么生成一个新节点并将其依附到一个社区，要么利用现有节点生成一条新超边。在生成每条新超边时，HMPA 首先采样一组社区，然后确定要从每个社区中选择的节点数量。在每个社区内，节点以优先依附的方式按照与其度成正比的概率被选择。
直观理解：社区结构是通过划分节点直接施加的。人们可以操纵采样概率以鼓励更多由少数社区甚至单个社区中的节点组成的超边，这意味着高模块度。
在这个生成器中，社区是不相交的，且社区成员资格是固定的。拥有更灵活的社区结构（例如重叠社区 [26, 41]（见 P12））可能是有益的。

G10. HYPERFF。HYPERFF 由 Kook 等人 [94] 提出，基于关于真实世界超图演化的观察（见 P25、P26 和 P27）。正如其名所示，该生成器的灵感来自于成对图上的森林火灾模型（forest fire model）[108]。

算法摘要：在每个时间步，一个新节点加入，并且选择一个现有节点作为大使节点（ambassador node），“森林火灾”由此开始。森林火灾通过现有的超边随机蔓延。当它终止时，从每个被“烧毁”的节点开始一场新的森林火灾，并且本轮被烧毁的节点与新节点共同形成一条超边。
直观理解：作者的动机来自于合著网络中的真实世界场景。在每个时间步，新节点代表加入研究社区的新学生，大使节点代表新学生的导师，而类森林火灾的过程代表了研究人员相互合作的真实世界过程。
Ko 等人 [92] 还开发了 HYPERFF 的一个简化且数学上易于处理的版本，这导出了关于期望超边大小、超边数量和节点度的闭式方程。然而，简化版本在复现真实世界模式方面的能力较弱，特别是关于直径收缩（见 P27）的模式。
HYPERFF 侧重于以宏观方式保留真实世界超图模式。进一步考虑微观模式（例如超边排序或重复）将是一个有趣的未来方向。

G11. THERA。THERA（transitive hypergraph generator，传递性超图生成器），由 Kim 等人 [88] 提出，基于关于真实世界超图传递性的观察（见 P10）。

算法摘要：节点被组织在具有多个层级的层次结构（具体而言，是一棵树）中，其中节点被划分为不相交的层级，更深（即更接近叶子）的层级包含更多节点，并且每个层级的节点被分割成不相交的群组。群组大小在不同层级间是相同的，因此在更深层级有更多的群组。在生成超边时，以某种概率，THERA 在群组内局部生成它，而以剩余概率，THERA 在整个节点集内全局生成它，其中较浅层级的节点更有可能被选择。
直观理解：社区结构（见 E12）自然地产生了高传递性（见 P10）。层次结构允许不同层级的节点以不同的概率被选择，这意味着现实的偏斜度分布，具体而言是大量的小度数节点和少量的大度数节点（见 P1）。
THERA 的超参数必须手动选择。如果有一个能自动选择超参数的拟合算法将是理想的。

5.2 子超图生成器

现在，我们介绍子超图生成器。与全超图生成器不同，子超图生成器输出给定超图的一个子图，同时保留某些性质。

5.2.1 静态生成器。我们将在下面介绍静态子超图生成器。

G13. MiDaS。MiDaS（minimum degree biased sampling of hyperedges，超边的最小度偏差采样），由 Choe 等人 [35, 36] 提出，旨在生成给定超边（注：原文此处疑似笔误，上下文应为超图）的代表性子超图，其中给定超图的性质（例如，P1、P4、P7、P8 和 P15）得到良好保留。

算法摘要：在 MiDaS 中，超边被逐个采样。每条超边的采样概率由其中的最小节点度决定。使用训练好的线性回归模型来自动调节对高度数节点的偏差程度。
直观理解：MiDaS 通过引入关于节点度的偏差扩展了随机超边采样。MiDaS 的设计动机来自两个观察：(1) 随机超边采样总体上效果良好，但无法生成具有高连通性（见 B3）和足够高度数节点（见 P1）的子超图，(2) 保留度分布与保留其他几个超图性质密切相关。
虽然 MiDaS 仅直接考虑关于节点度的偏差（见 P1），但它保留了许多其他超图性质（例如，P4、P7、P8 和 P15）。
研究保留节点度与保留其他超图性质之间强联系背后的深层原因将很有趣。此外，考虑时间信息（如果可用）可能有利于性能。

G14. HRW。HRW（hybrid random walk，混合随机游走），由 Zhang 等人 [182] 提出，使用通过超图上的随机游走进行采样。采样的（即访问的）节点和超边用于估计输入超图的统计量，例如节点度和超边大小分布（见 B4）。

算法摘要：HRW 通过具有单独节点和超边转移的马尔可夫链蒙特卡洛（MCMC）获得节点和超边样本。输入超图的统计量基于采样的节点和超边进行估计。
直观理解：在超边上朴素地构建马尔可夫链具有高的时间和空间复杂度。HRW 分离了节点和超边转移，以避免考虑节点和超边的组合，从而降低了状态空间的复杂度。
他们还提出了提高 HRW 采样效率和估计准确性的技术。这些技术包括使用提升马尔可夫链（lifted Markov chains）[31] 的非回溯策略以加速收敛，以及跳过策略以加速转移。

5.2.2 动态生成器。我们现在将介绍动态子超图生成器。

G15. TRHC。TRHC（temporal reconstruction hill climbing，时间重构爬山法），由 Comrie 和 Kleinberg [40] 提出，主要基于关于超图自我网络的观察（见 P21、P22 和 P23）。

算法摘要：给定一个自我网络，TRHC 为给定自我网络中的超边分配时间顺序。从初始顺序开始，TRHC 不断交换超边对以提高不同顺序的“适应度”（fitness），其中“适应度”由监督模型评估。当无法再改进时，过程终止。
直观理解：监督模型经过训练，以便它应该给更好地匹配观察的时间顺序更高的“适应度”值。因此，提高“适应度”应该使时间顺序更类似于观察到的模式。
该生成器仅限于预测完全给定的一组超边的顺序，并且也仅限于超图自我网络。此外，在真实世界场景中，一组超边的多个不同顺序可能同样可能且现实。研究偏序（例如，因果关系 [120]）可能是一个有趣的方向。

G16. CRU。CRU（correlated repeated unions，相关重复并集），由 Benson 等人 [17] 提出，主要基于关于真实世界时序超图中时间行为的观察（见 P17 和 P20）。

算法摘要：CRU 以顺序方式生成子超图（例如，星型自我网络；见 E5）中的超边。对于每条新超边，假设其大小和其中此前从未出现过的新节点数量是已知的。为了找到剩余节点来填充超边，CRU 从现有超边中采样一条超边，其中较近的超边更有可能被选择。所选超边中的每个节点以采样概率 p p独立地复制到新超边中，直到新超边被填满。如果新超边未被填满，则重复相同的过程。
直观理解：从现有超边采样建立了新超边与现有超边之间的时间相关性（见 P17）。时间局部性的程度由对近期超边的偏差控制，而相关性的程度（即子集的重复）由采样概率 p p 决定。
所需的输入信息包括每条新超边的大小和其中新节点的数量，这可能是不现实地强的。用较弱的预言机（oracle）保留所考虑的模式将是一个具有挑战性但有趣的未来方向。

6 未来应用与方向

在本节中，我们讨论超图挖掘，尤其是超图模式的未来应用与方向。我们主要讨论与图挖掘相关的现有应用与研究主题，特别是本综述所讨论内容的图论对应物。由于大多数超图模式是从图模式推广而来的，我们预计图挖掘的许多现有应用与方向在未来也将被扩展并推广至超图。有关包含更多参考文献的深入讨论，请参阅补充文档 [1]。

6.1 在算法设计中的应用

图挖掘模式已启发了面向真实世界应用的创新图算法，我们预计这些应用可以扩展至超图挖掘。

度分布。关于真实世界图通常表现出重尾度分布的观察已被用于图算法的设计，包括分布式图算法 [149]、图遍历算法 [180] 等。基于超图中的类似模式（见 P1 和 P15），上述应用有可能扩展至超图。

时间局部性。在许多真实世界时序图中，观察到时间局部性，即在较小时间窗口内出现的边更有可能相互交互。这一性质已被用于设计用于三角形计数 [100] 和图遍历 [93] 的高效算法。在超图中已观察到几种与时间局部性相关的模式（见 P17 和 P21），我们预计此类模式将有助于时序超图算法的设计。

直径。真实世界图中的小直径已被考虑用于设计大规模图挖掘算法 [83]。因此，在真实世界超图中观察到的收缩直径（见 P27）也可能有助于大规模超图挖掘。

6.2 在机器学习中的应用

图模式也已被广泛用于图上的机器学习，这暗示了超图模式在超图机器学习中的潜在有用性。

图神经网络与通用特征表示。图上机器学习中最常见的主题之一是特征表示，其中图神经网络（GNNs）常被使用。许多图性质与模式已被考虑用于增强 GNN 的性能，包括度分布 [115] 和同配性 [158]。我们预计超图模式将像其图论对应物一样，在（超）图神经网络以及超图中的通用特征表示方面发挥作用。

链路预测与社区发现。链路预测和社区发现是图上两个传统的机器学习问题。许多图模式已被用于这两个问题，包括同配性 [39] 和图模型 [145]。我们期待看到超图模式被用于这两项任务。

异常检测。异常检测是另一个传统的机器学习问题，而基于图的异常检测 [3] 是一个流行的子主题。许多图模式已被用于基于图的异常检测，包括图模体 [135] 和 k k-核 [155]。我们预计超图模式在此应用中会有更多用途。

推荐系统。图是构建推荐系统的重要工具，推荐系统是机器学习中一个长期存在的研究主题，其中许多图模式已被使用，包括图模体 [65] 和自我网络的结构 [48]。超图对于此任务也很有用，尤其是捆绑推荐（bundle recommendation）[184]。我们期待超图模式在推荐系统中得到更多应用。

6.3 广义超图的分析与挖掘

在本综述中，我们主要讨论了简单超图（即无向且无权的超图）。下面，我们希望讨论几种类型的广义超图。

有向超图。有向超图（其中每条超边内的节点被划分为源集和目标集）已在数学和理论计算机科学领域得到研究。最近，Kim 等人 [89] 将互惠性（reciprocity）的概念扩展到了有向超图，并研究了真实世界有向超图中的相关模式。我们预计将在有向超图上探索更多模式。

加权超图。本综述中提到的大多数工作处理的是无权的真实世界超图，或明确地将数据集预处理为无权超图，尽管有些工作考虑了超边的重复 [17, 103]。最近，学界对具有边依赖节点权重（即一个节点在不同超边中可以具有不同权重）的超图也日益感兴趣 [32]。我们预计将在加权超图上探索更多模式。

7结论

超图是一种宝贵的数学框架，用于建模各种真实世界场景中复杂的群体交互。超图固有的复杂性既为超图挖掘带来了机遇，也带来了挑战，而超图挖掘最近已日益受到关注。本综述全面考察了迄今为止超图挖掘领域的进展，并对超图的模式、工具与生成器提供了全面的概述。我们还提出了完整的分类体系，以增进对各个方面的结构化理解。最后，我们提出了若干研究方向。我们希望本综述能为研究人员和从业者提供宝贵的资源与见解，从而推动超图在各领域的基础研究与实际应用的发展。

原文链接：https://arxiv.org/pdf/2401.08878v2