生成式超图聚类:从块模型到模块化

  |  

文章导航

Science Advances 2021 生成式超图聚类:从块模型到模块化。阅读报告

生成式超图聚类:从块模型到模块化

——by Zehua Ren

Chodrow P S, Veldt N, Benson A R. Generative hypergraph clustering: From blockmodels to modularity[J]. Science Advances, 2021, 7(28): eabh1303. SCIADV2021 31引用

0 摘要

提出了一种具有异构节点度和边权重的聚类超图的概率生成[1]模型,使用该模型的近似最大似然推断得到聚类目标——概括表示了当今流行的图模块度优化目标。推导出了一种推理算法,该算法推广了 Louvain 图社区检测方法,以及一种更快更专业的变体,其中边预计完全位于集群内。使用合成和经验数据,证明了这种专门的方法具有高度可扩展性,并且可以检测基于图的方法失败的集群。在真实数据集上找到了可解释的高阶结构

1 绪论

复杂数据中的大部分结构同时涉及两个以上实体之间的高阶交互和关系——图的推广:超图

图聚类:通过将其节点划分为密切相关或相互关联的组(也称为集群或社区)来描述大型图。超图聚类方法在许多领域都有应用:并行计算、电路设计、图像分割、半监督学习、基因表达高阶网络分析、食物网、在线社交社区。

一种成熟的图聚类方法是将图建模为来自概率生成模型的样本,在这种情况下,聚类任务可以重铸为统计推理问题。但是现如今缺乏超图的生成技术,通常生成的超图只有一种尺寸的边,没有对节点之间的度异质性进行建模(2021年一篇解决得比较好)。边尺寸节点度的异质性都是超图的重要特征。

  • 有一种生成式超图聚类方法是通过连通分量扩展[2](clique expansion)将超图转化为二元图[3](dyadic graph),虽然这使得可以使用广泛的现有模型和算法用于图,但高阶结构丢失了,并且二元图的生成模型可能依赖于明显违反的独立性假设。

    最近,已经为超图推广了基于流行的图模块化聚类目标的非生成方法,但它们缺乏与生成模型的关联,限制了它们的可解释性。——是我们之前使用的方法

  • 生成聚类的另一种方法是将超图的表示为二分图[2],将生成模型应用于二分图上。涉及一个强有力的假设:给定超边中任何两个节点的成员资格都是独立的,取决于模型参数。——八卦之类的交互通常只发生在受信任的个人之间。一个不请自来的局外人的存在可能会完全阻止互动的发生。这些交互的“全有或全无”(AON)结构严重违反了大多数二分生成模型所做的条件独立性假设。我们的场景也可能不适用

本文提出了一种基于度数校正的超图随机块模型[4](DCHSBM)的超图聚类生成方法,该模型生成具有异构度分布和超边大小的聚类超图。概述了一种用于将该模型拟合到超图数据的近似坐标上升[5]最大似然估计方案,并说明该方案的一个阶段概括了经过充分研究的图模块化目标。为此类模块化目标派生了伴随的 Louvain 算法,这些目标在重要的特殊情况下具有高度可扩展性。实验表明能够在基于图的方法由于已知的理论限制而必然失败的情况下检测到集群。在具有适当匹配的高阶结构的数据集中,生成超图技术能够以比基于图的技术更高的速率恢复与元数据相关的集群。结果强调了将生成模型与数据集匹配的重要性,并指出了在高阶网络科学中进一步工作的一些方向。

2 材料和方法

2.1 DCHSBM模型

度数校正随机块模型 (DCSBM) 是具有社区结构和异构度数序列的图的生成模型。——将其推广到超图

是超图中的节点数,每个节点 被分配到 个组之一,表示节点的组分配,放在向量中。与二元 DCSBM 一样,每个节点 都分配有一个参数 来控制其度数,放在向量 中。令 表示无序节点元组的集合,因此每个 是一组表示可能超边位置的节点(遵循图中 DCSBM 的标准选择,我们允许 包含具有重复节点的节点元组) .令 表示给定元组 中节点的组标签向量,而 表示度参数向量

我们使用亲和函数 来控制在给定节点元组 上放置超边的概率,这取决于 中节点的组分类情况。形式上,将组分配 映射到非负数。如果 很大,则在 中的节点之间形成超边的概率更高。在我们的模型中,放置在 处的超边数分布,其中 表示对 中的节点进行不同排序方式的数量度数参数的乘积。实现给定值 的概率为: 边生成过程的直观解释:对于 个可能的节点排序的任何一个,我们尝试在这个元组上放置符合泊松分布 数量的超边。最终得到无序元组 上的加权超边,其权重可以是任何非负整数。这是一个有用的建模功能,因为许多经验超图在同一组节点之间包含多个超边。即使在我们只知道是否存在超边(但不知道权重)的超图数据集中,基于泊松的模型也可以作为基于伯努利的模型在计算上的方便近似。实现给定超边集 的概率就是每个 上的概率的乘积。

2.2 度估计和亲和参数

在一般随机块模型 (SBM) 及其亲属中有许多推理方法:变分坐标上升、变分置信传播和马尔可夫链蒙特卡罗等。本文通过坐标上升执行近似最大似然推断。将DCSBM最大似然推断与图聚类中流行的模块化目标相结合。坐标上升框架,是块模型推理的期望最大化(EM)算法的近亲EM算法构建“软”集群,每个节点在每个集群都有一个可能性,取最大可能;坐标上升法生成“硬”集群,其中每个节点恰好属于一个集群。轮廓似然方法(Profile likelihood methods)为最大似然推断提供了一个替代框架,可能是未来研究的方向。

在最大似然框架中,我们通过求解优化问题来学习节点标签的估计 、亲和函数的估计 和度参数的估计 其中 是由(整数加权)超边集合表示的给定数据集。像往常一样,使用具有相同局部最优值的对数似然更容易。对数似然是: 其中:

第一项 是对数似然取决于组分配 和亲和函数 的唯一部分。第二项取决于 ,而第三项仅取决于数据 ,并且可以出于推理目的而忽略。

在最大似然的坐标上升方法中,我们在两个阶段之间交替。在第一阶段,我们假设当前估计 并通过求解下式得到新的 估计: 结果对 可以被视为最大似然估计,以标签向量 的当前估计 为条件。在第二阶段,我们假设当前估计 并通过求解得到新的 估计: 我们在这两个阶段之间交替,直到收敛。

需要解决几个可识别性[6]问题

  1. 首先,排列 中的组标签不会改变似然值。因此,我们对组标签施加任意顺序
  2. 其次,可能的组数 原则上可以大于 中存在的组数。这种情况对应于存在统计上可能但在给定数据实现中为空的组。虽然其他处理方法是可能的,但我们选择忽略空组,将 的数量等于 估计中不同组的数量。
  3. 不可识别性(unidentifiability)的最终形式与 的尺度有关。对于固定的 ,我们可以构造 使得 (补充附录 A)。因此,为了确保可识别性,我们必须在 上设置一个联合标准化条件。我们选择约束 使得:

其中 并且 是节点 出现的超边的(加权)数。在此表达式及以下表达式中, 是一个指示函数,如果其所有输入都相等,则其值为 1,否则为 0。

公式(9)的用处是,当 已知或估计时,公式(7)中对 的条件最大似然估计采取简单、封闭的形式。

首先,对于固定标签向量 ,当使用标准化(9)时, 的最大似然估计为(见补充附录 B)

其次,以 为条件,如果 在一些无序标签元组 上取恒定值 ,则 的最大似然估计为(见补充附录 C)

总的来说,我们可以为数据中每个可能的标签元组估计一个这样的 。稍后,我们将对进行自然限制。虽然公式(10) 假设 是固定的,不必知道 来生成估计量 。然而,通过 公式(11) 生成估计量 需要我们知道或估计 。所以要记住 不是全局最优估计,而是以当前估计的组标签为条件的局部最优估计

公式 (11) 也可以直接插入到完全似然最大化问题 (2) 中,消除与 对应的参数并产生低维轮廓似然,原则上可以直接进行优化。这种方法对于二元块模型(普通图)是成功的,为超图块模型开发的类似方法将大有研究空间。坐标上升框架的优势在于

  • 我们能够通过推广常见图聚类最大似然超图Louvain算法,以开发快速启发式算法来很好地解决问题 (8) 。
  • 在我们的框架中解决问题 (7) 也可以解释为评估固定聚类向量 轮廓似然性[7],突出了这些方法之间的关系。

我们现在研究推断标签向量 的问题。这个问题自然地引出了超图聚类的一类模块化目标。

2.3 对称模块度

上一节的结果表明,估计的度参数 和分段常数亲和函数 可以以封闭形式有效地估计,从而提供对 的估计。这为坐标上升的第一阶段公式 (7) 提供了解决方案。我们现在讨论第二阶段公式(8)。从等式 (3)可以看出,就为了估计优化 就足够了。为此, 上施加一些额外的结构是有帮助的。

我们通过规定 关于节点标签的排列对称来获得一类重要的目标函数。在这种情况下, 不取决于给定节点元组 中的特定标签 ,而仅取决于每个标签的重复次数。在统计上,相应的 DCHSBM 生成超图,其中所有组在统计上相同,取决于其组成节点的度数。因此,对称亲和函数将种植分区 SBM算法(planted partition SBM)灵活地推广到超图上。

定义函数 ,其中 是在 中的第 号最大分组在本次标签向量中出现的条目数,可以任意断掉连接。例如,如果 ),则 。我们称 为分区向量。对称假设意味着 的函数,仅通过 和它建立连接。因此,当 时,我们通过定义 符号滥用[8]

我们现在为 个节点的元组定义对应于可能的分区向量 广义割(generalized cuts)和广义体积(generalized volumes):

其中 中由 个节点组成的元组子集。函数 计算被 分割到指定分区 中的边数,而函数 是诱导出分区 的所有分组向量 上的体积的和积。令 为在大小为 的集合上的划分向量集,即超边的最大大小。我们在补充附录 D 中表明,对称模块化目标可以写为:

对于 个节点的元组的分区向量 ,直接计算 个元素的总和,当 很大时,这可能是不切实际的。不过,我们在补充附录 E 中表明,可以通过组合恒等式有效地评估这些总和。我们还给出了一个公式,用于在修改候选标签时更新体积项

目标函数 (14) 与最近提出的多路超图切割问题相似。他们根据分割函数制定超图切割目标,当边缘在两个或多个集群之间分裂时,这些函数将进行惩罚。然后,目标是最小化惩罚的总和,约束条件为为某些节点不得位于同一集群中。我们框架中的对称亲和函数(在其术语中对应于基于签名的分割函数表 1 列出了许多亲和函数系列中的四个。

表 1. 对称亲和函数。在整个过程中, 是分区 中的节点数, 是标量, 是任意标量函数。

亲和函数类型 公式
全有或全无 (AON)
分组数量 (GN)
相对复数 (RP)
节点对
  1. 全有或全无(AON) 亲和函数仅区分给定边是否完全包含在单个集群中。这种亲和力函数对于可扩展计算尤其重要,我们将在下面进一步讨论。
  2. 分组数量 (GN) 亲和性仅取决于边缘中包含的不同组的数量,而与每个组中的事件节点数无关。 GN 亲和函数在应用中经常出现特殊情况。当 时,模块化目标的第一项对应于超边切割惩罚,在科学计算文献中称为“连通性-1(connectivity − 1)”、K-1 度量(the K–1 metric)或边界切割(boundary cut)。它在数据库文献中也被称为扇出(fanout)[9]。相关的外部度数总和惩罚也是 GN 亲和函数的一个特例。
  3. 相对复数 (RP) 亲和函数仅考虑边缘中表示的最大组的大小与下一个最大组的大小之间的相对差异。这种相当专业的亲和函数特别适用于分组大致平衡的情况,例如,我们在国会委员会的党派关系中发现。
  4. 节点对亲和函数计算边缘内分组不同的节点对的数量。虽然此亲和函数使用与二元图模型使用相似的信息,但在任何二元随机图和具有节点对亲和函数的 DCHSBM 之间没有立即明显的等价性。
  5. 还有更多对称的亲和函数;可用于定义亲和力的其他拆分函数见文献52的表三。

块模型和模块化度之间的关系最近在文献56中得到了关注。这种思考也适用于我们对上文公式(14)和下文公式(15)的推导。我们在一般的、无约束的亲和函数 的假设下推导出了 的条件最大似然估计 (10) 和 (11)。当施加额外的约束——例如对称约束——时,就不能保证这些相同的估计使可能性最大化。在二元图的情况下,用于估计 的公式(10)和公式(11), 在 的对称假设下仅当 对于每个 是常数时是精确的。当组的大小不同时(这在大多数数据集中都是典型的),公式 (10) 和 (11) 是精确的条件最大似然估计的近似值。这种情况让人想起图模块化目标倾向于生成大小大致相等的分组。因此,我们在下面提出的目标函数和算法应该被理解为坐标上升最大似然推断的近似值,这仅在所有集群具有相等体积的情况下才是准确的。

2.4 AON 模块度

——全有或全无模块度

建模和计算对AON 亲和函数特别感兴趣。对于相互作用或关系的发生在很大程度上取决于组同质性的系统,这种亲和函数是一种自然选择。

将表 1 中的 AON 亲和函数插入公式 (14), 经过一些代数计算(补充附录 F),得到目标函数:

其中 集合了不依赖于分区 的项。我们将 收集到向量 中。我们还定义了:

在这个表达式中, 是大小为 的超边的(加权)个数,即 。因此,切割项 计算大小为 的包含两个或多个不同簇中的节点的超边的数量。该计算是最近提出的图模块化方法的直接推广。我们通过限制 来恢复到标准的二元模块化目标函数。我们称公式(15)是 AON 超图模块度

最近,有研究提出了超图的“严格模块化”的优化目标函数。这种严格的模块化是公式 (15)的一个特例, 通过选择 使得 ,其中 是超图中所有节点度的总和。然而,保留这些参数为我们提出的 AON 目标方程 (公式15)提供了重要的灵活性。调整 允许指定哪些超边大小被认为与聚类最相关。例如,在电子邮件通信中,一个非常大的收件人列表可能携带关于他们的社会关系的最少信息,并且可能需要降低大型超边的权重。调整 具有修改目标函数偏爱的集群大小的效果,直接概括了二元模块化中的分辨率参数。不必事先指定这些参数的值;相反,它们可以通过公式(11)自适应地进行估计。

2.5 超图最大似然鲁汶-HMLL

为了优化模块化目标函数(14)和(15),我们提出了一系列凝聚聚类算法。这些算法通过对节点标签向量 的局部更新来贪婪地改进指定的目标。这些算法的结构基于广泛使用的高性能启发式图算法: Louvain。标准启发式在两个阶段之间交替。在第一阶段,每个节点都从自己的单例集群开始。然后,每个节点 被访问并移动到相邻节点 的集群中,使目标 的增量最大化。如果没有这样的移动增加目标,那么 的标签不会改变。重复此过程,直到不存在增加目标的此类动作。在第二阶段,为每个标签形成一个“超级节点”。超级节点代表共享该标签的所有节点的集合。然后,重复第一阶段,生成更新的超级节点标签,然后在第二阶段聚合。重复该过程,直到无法再改进为止。因为第一阶段的每一步都改进了目标,所以算法以局部最优聚类向量 收敛。

这种启发式可以自然地推广到超图的上。然而,异构超边大小和一般亲和函数的结合使实现变得相当复杂。

在这里,我们提供了一种高度通用的超图最大似然 Louvain (HMLL-hypergraph maximum likelihood Louvain) 算法,用于优化对称模块化目标 (14)。对于 AON 亲和函数的重要案例,简化的目标 (15) 采用了更简单、更快的专用 Louvain 算法,我们在补充附录 G 中对此进行了描述。正如我们在后续实验中所展示的,这种专用算法具有高度可扩展性,并且可以有效地恢复由 AON 亲和函数合理建模的多元结构数据集中的真实集群。

2.6 对称HMLL

  1. 我们的对称 HMLL 算法的第一阶段对映标准图上的 Louvain:节点从单例集群开始,然后贪婪地移动到相邻的集群,直到无法再增加模块度。
  2. 普通图 Louvain 的第 2 阶段以保持结构的方式将集群之间的边简化为超节点之间的加权边。然而,在超图的情况下,简单地折叠集群和超边会丢弃有关超边大小和每个超边在集群之间划分方式的重要信息。因此,在我们算法的后续阶段,我们通过移动原始超图中的整个节点集来贪婪地改进目标,而不是贪婪地移动单个节点。这样,在先前迭代中分配给同一集群的一组节点本质上被视为超级节点(supernode)并作为一个单元移动,而不会折叠超图并丢失有关超边结构的所需信息。

我们的整个过程在算法 S1 和 S2 中进行了形式化。算法 S1 依次访问上一次迭代的集群 的每组节点 。该算法评估与将所有 移动到相邻簇时,关联的目标函数 的变化量 ,然后执行使目标具有最大正变化的移动。重复此过程,直到移动任何一组 不再能改善目标。整个对称 HMLL 方法通过算法 S2 进行总结,该算法首先将每个节点放在一个单例集群中,然后再调用算法 S1。(——S1单步,S2整体)

算法 S1 依赖于一个函数 ,该函数计算与将所有从 中的节点移动到相邻集群后相关的目标 Q 的变化。使用组合恒等式可以有效地计算目标中第二项(体积)的变化(补充附录 E,命题 1)。对第一个(割)项的变化需要对一个节点或一组节点的所有超边求和。在每个超边,我们必须评估当前分区 上的亲和性 ,以及与候选更新分区 相关联的亲和性 。这种情况与普通图 Louvain 算法的情况形成对比,在原算法中,检查给定边是否连接相同或不同集群中的节点就足够了。我们需要为每个超边存储和更新分区向量 的事实阻止了我们将节点集群折叠成一个单一的超级节点,并在简化的数据结构上递归地应用算法 S2,而这在普通图 Louvain 中很常见。

因此,虽然节点集群在算法 S1 中也作为一个单元移动,但在这种情况下,有必要在算法的所有阶段对完整的邻接数据 进行操作。这可以使算法 S2 在即使是中等大小的超图上也很慢。开发用于优化一般对称模块化目标或各种特殊情况的有效算法是未来工作的重要途径。

2.7 AON HMLL

是 AON 亲和函数时,可以进行相当大的简化。对于每条边,我们不需要计算完整的分区向量 ,而只需检查 是否成立。我们不是提供一般的亲和函数 ,而是提供出现在公式 (15)中的参数向量 。这使我们能够在相当简化的数据结构上进行计算。特别是,我们能够遵循经典的Louvain策略,将集群折叠成单个合并的超级节点,并将注意力限制在跨越多个超级节点的超边上。因为我们不需要跟踪超边跨越多个超节点的精确方式,所以我们可以忘记大部分原始邻接数据 ,而是简单地存储超图的边大小。这些简化既可以节省大量内存,又可以非常快速地评估目标更新函数。我们在补充附录 G 中提供了这些简化算法的伪代码。


补充附录G

上一节我们给出了通用对称亲和函数 (算法 1 和 2)的超图最大似然鲁汶(HMLL)的伪代码。对于 All-Or-Nothing 亲和函数的特殊情况,可以获得相当快的 Louvain 算法。特别是,可以遵循经典的二元 Louvain 的“超级节点”策略,能够在比原始邻接超边矩阵更简单的数据结构上进行计算。算法 1 描述了 AON HMLL 的外循环。整体结构与内循环算法 2 中的大致相同。在外循环的每次迭代中,我们使用函数 初始聚类 折叠成简化的超图这种方式仍然保留了特殊的 AON 结构。我们在简化超图上运行 Louvain 步骤,然后使用函数 将简化超图上的聚类 转换为原始超图上的聚类 如果 重合,则 Louvain 步骤没有发现任何改进,我们终止。否则,我们开始一个新的迭代,首先在运行 Louvain 步骤之前将更新的聚类折叠成一个简化的超图。在构造简化表示 时,有必要仅将折叠的超图与每个边的原始大小的向量 一起存储。每个折叠节点 的度数 只是相应集群 中节点的度数之和。

Louvain 步骤本身由算法 2 给出。在每个阶段,我们检查折叠节点 并计算与将 更改为 时相应目标函数的变化,其中

是通过设置 而其他条目保持不变获得的折叠标签向量。该计算包含在子程序 中。

值得注意的是,在一般对称HMLL算法 1 中, 的计算比 快得多。公式(15)中体积项的局部变化只需要更新集群体积的幂和,由分辨率参数 进行放缩。更新公式(15)的割项需要对与要更新的节点 相邻的每个超边的切割状态的变化求和。在 AON 设置中,只有两种可能的状态——剪切和未剪切。检查一条边是否被切割比在可能移动之前和之后计算超边的精确分区向量要容易得多。因此,此步骤在实践中比计算对称目标的切割变化要快得多


2.8 集群数

与大多数 Louvain 风格的模块化方法一样,用户无法直接控制 HMLL 返回的集群数量。影响聚类数量的一种方法是手动设置亲和函数 或参数 的值(如果使用 AON 亲和性)。与其从数据中推断这些参数,不如先验地设置它们并在 上执行一轮迭代优化获得。这种方法将二元图模块度最大化中分辨率参数的常见处理推广为调整超参数,而不是从数据中估计的数字。可能需要大量的实验来获得所需的集群数量,并且可能无法检索到确切的数量。

影响集群数量的另一种方法是在社区标签上施加贝叶斯先验。在贝叶斯方法的最简单版本中,假设在对边进行采样之前,每个节点都以相等的概率独立地分配了一个 标签。实现给定标签向量 的概率为 ,它在对数似然 中生成形式为 的项。该术语接下来可能会被合并到 Louvain 实现中,结果是会强烈激励减少集群总数 的贪婪动作。然后,生成的正则化算法可以用稍微较少数量的不同簇来标记向量 。当先验地知道数据中的真实集群数量很少时,这可能很有用。我们对 AON HMLL 的实现包含了这个可选的正则化项。我们仅在下面介绍的合成可检测性实验中使用该术语。——(?没看懂)

3 结果

3.1 运行时间

二元(Dyadic)Louvain 算法以在大图中高效而闻名。在这里,我们展示了 AON HMLL 可以在合成数据上实现与图 MLL (GMLL) 相似的性能——这是标准二元 Louvain 算法的一种变体——其中我们返回产生最高二元似然的分辨率参数和分区组合。对于固定数量的节点 ,我们考虑一个类似 DCHSBM 的超图模型,包含 个集群和 个超边——超边大小 均匀分布在 2 和 4 之间。每个大小为 的边以概率 均匀地随机放置在同一集群内的任意 个节点上。否则,以 的概率,将边随机均匀地放置在任意 个节点的集合上。我们使用这个模型而不是直接的 DCHSBM 来避免在每个 元组节点上采样边的计算负担,这在 很大时是禁止的。出于性能测试的目的,我们使用真实聚类标签计算参数向量 (在 AON HMLL 的情况下)和分辨率参数 (在 GMLL 的情况下)的估计。我们强调这在实际应用中通常是不可能的,因为真实标签是未知的。我们做出这个选择是为了专注于在两种算法都能成功的情况下直接比较每种算法的运行时间。在后面的部分中,我们研究了 HMLL 和 GMLL 在亲和力和分辨率参数未知时恢复合成和经验数据中已知组的能力。

图 1 显示了当 时在合成超图上返回的运行时间、调整兰德指数 (ARI) 和聚类数。选择这些参数以使大小为 3 和 4 的超边很少(如果有的话)完全包含在簇内。因此,不同大小的超边提供了关于真实聚类的不同信号。在这个实验中,我们通过计算标准化团投影(normalized clique projection)——连通分量扩展为普通图来实现 GMLL,其中节点通过带权重的加权二元边连接: 我们还对 的非标准化团投影进行了实验,但没有显示这些结果,因为在这个实验中,相关的 MLL 算法始终无法恢复与种植分区相关的标签。

根据 ARI 的测量,在较小的实例上,HMLL 在恢复种植集群方面的表现优于 GMLL。对于较大的实例,恢复结果类似。尽管 GMLL 和 HMLL 在本实验中获得了相似的准确性,但它们以不同的方式实现,HMLL 倾向于生成比 GMLL 更多、更小的集群。运行时间几乎没有区别,这表明二元团投影(连通分量扩展)对于准确性和性能都不是必需的。我们观察了参数 的其他选择对结果的影响,其中 HMLL 在集群恢复方面的性能大大优于 GMLL,反之亦然;然而,在每种情况下,算法各自的运行时间往往只相差很小的常数因子。

簇内边缘放置概率为,以浅灰色显示了使用 GMLL 作为预处理步骤,然后通过 HMLL细化其输出分区获得的结果。

在这个综合实验中,两种算法的组合实现了最强的恢复结果。除了独立运行每个算法之外,我们还运行了一个两阶段算法,其中使用 GMLL 生成中间分区,然后使用 HMLL 对其进行细化。我们再次强调,这些结果是在具有预先优化的亲和力参数的合成超图上获得的,因此细化策略的有效性可能无法推广到真实数据集。在下面显示的经验数据实验中,我们没有显示细化过程的结果,因为在每种情况下,组合方法的输出分区与二元方法的输出分区基本上无法区分。这可能反映了这样一个事实,即我们没有让算法先验地学习与真实数据标签相关的亲和力参数。进一步研究混合策略的性能将具有相当大的实际意义。

3.2 超图扩展(二元投影)和可检测性阈值

非正式地,当该算法的输出标记 以高于零的概率与 相关时,该算法能够在具有固定标签 的随机图模型中检测社区。使用统计物理学的论据,文献(45) 的作者推测在图 SBM(随机块模型) 中存在一个没有算法可以成功检测社区的机制。这个猜想后来在各种特殊情况下得到了提炼和证明;参见文献 (61) 的综述。在具有两个相等大小的种植群落的二元 SBM 中,大图中可检测性的必要性限制条件是: 其中 是连接到节点的簇内边的平均数,而 是连接到节点的簇间边的平均数。如果不满足此条件,则没有算法可以可靠地检测关联图 SBM 中的社区,尽管社区在统计上是不同的。该界限限制了直接推理方法,例如贝叶斯或最大似然技术,以及基于模块化或其他图目标函数最大化的方法。最近的几篇论文考虑了均匀超图的可检测性问题。在我们的模型中,存在多种尺寸的边使分析变得复杂。在这里,我们将自己限制在一个实验证明中,即图 SBM 和我们的 DCHSBM 的可检测性机制可能存在显着差异

图 2 显示了在一个简单的 DCHSBM 上进行的两个实验,其中有两个大小相等的社区,每个社区有 250 个节点。对亲和力 进行了调整,使得:

  1. 每个节点平均与 5 个 2 节点边和 5 个 3 节点边相关。
  2. 2 节点边的一部分 连接同一集群中的节点,而 2 节点边的一部分 连接不同集群中的节点。

  3. 3 节点边的一部分 连接同一集群中的节点,而 3 节点边的一部分 连接不同集群中的节点。

对于* 是大小为 i 的簇内边缘的比例。每个像素给出 20 个独立生成的大小为 n = 500 的 DCHSBM 的平均 ARI,其中每个节点平均与 5 个 2节点 边和 5 个 3节点 边发生关联。 (左)从 GMLL 获得恢复的分区 。 (右)从 AON HMLL(算法 S1)获得恢复的分区。虚线和点线给出了正文中描述的各种可检测性阈值。在每个面板中,返回的分区 是在更新 和相似性参数推断之间的 20 次交替中的最高似然分区。仅在这个实验中,我们在模块化目标中加入了一个正则化项 ,以促进生成具有更少簇的标签向量


这部分看不懂

仅在这个实验中,下面讨论的 GMLL 和 AON HMLL 都在似然目标中使用贝叶斯正则化项 ,以促使每个算法形成相对较少数量的集群。在左侧面板中,我们展示了使用 GMLL 的非标准化变体时返回的分区 与真实分区 的 ARI(标准化变体的结果相似)。这种选择反映了这样一个事实,即真实的簇数是已知的并且等于 2。白虚线和白点线给出了等式(18)成立的边界。白虚线给出了分类机制的可检测性阈值,其中节点更有可能与同一集群中的其他节点链接。 Louvain 作为一种聚类算法,非常适合检测分类簇,并且能够在该机制的大部分(但不是全部)中检测社区。理论阈值与 Louvain 性能之间的差距反映了 Louvain 作为一个阶段性贪心算法没有最优性保证的事实。在白点线下方还有一个不可检测的区域。基于图的 Louvain 的凝聚结构导致算法在这里完全失败。

在右侧面板中,我们展示了使用 AON HMLL 的相同实验。虚线 分别给出了完全忽略 3 节点边和 2 节点边的假设算法的分类可检测性阈值,而点线 给出了相应的不可检测阈值。 HMLL 能够检测种植分区的一系列参数值,而 GMLL 不能。其中包括某些大小的边主要位于簇间的情况,如左上角( 小)和右下角( 小)所示。有一个机制(中和右下),其中算法似乎受到边界 q2 的约束,这表明 HMLL 有效地忽略了该机制中的 3 节点边。然而,随着 的增加,3 节点边变得更具信息性,并且可以在 的分区(右上角)检测到某些值。还有一个广泛的机制(左上角),其中超图算法能够有效地使用 2 节点和 3 节点边来检测集群,即使 2 节点边主要在集群之间。我们还观察到 HMLL 在 2 边和 3 边都在簇间(左下)的情况下检测簇的能力非常有限。因为 HMLL 又是一种凝聚算法,所以它对诸如此类的完全不分类分区的性能充其量是不可靠的。

有趣的是,还有 的组合,其中 GMLL 能够检测到种植分区,而 HMLL 则不能。这可能表明二元投影所暗示的不同大小的边的汇集在某些情况下可能是有用的。我们再次注意到 GMLL 和 HMLL 都不是最优推理算法。最佳超图算法可能会显着扩展图 2 右侧面板中的可检测范围。我们将这些算法的开发及其分析视为未来研究的极有希望的途径。


3.3 经验数据上的实验

接下来,我们分析了从经验数据中得出的几个超图。

  • 前两个是人类近距离接触交互的超图,从小学和高中的可穿戴传感器数据中获得。节点是学生或老师,超边连接彼此靠近的人群。节点标签标识每个学生所属的班级,小学数据还包括与每个班级关联的老师。
  • 接下来,我们从美国国会法案共同提案数据中创建了两个超图,其中节点对应于国会议员,超边对应于众议院或参议院法案的发起人和所有共同发起人。
  • 我们以委员会成员的形式从美国国会构建了另一对数据集。每条边都是国会会议中的一个委员会,每个节点又对应于众议院议员或参议员。如果相应的立法者在指定的国会会议期间是委员会成员,则节点包含在边中。包含了跨越 1993 年至 2017 年从第 103 届至第 115 届的所有国会议员。众议院和参议院成员仍然有单独的数据集。在所有国会数据集中,节点标签给出了成员的政党。
  • 我们还使用了沃尔玛购买的超图,其中每个节点都是一个产品,超边连接了客户在一次购物之旅中共同购买的一组产品。每个节点都有一个关联的产品类别标签。
  • 最后,我们构建了一个超图,其中节点对应于 trivago.com 上列出的酒店,每个超边对应于一组酒店,其网站被 Trivago 的用户在浏览会话中点击。该超图源自 2019 年 ACM RecSys 挑战赛发布的数据。对于每家酒店,节点标签给出了它所在的国家/地区。数据集的大小在节点数量、超边、超边大小和节点标签方面有所不同(表 2)。

表2. 研究数据集摘要。显示了节点数 、超边数 、平均度 、度数的标准差 、平均边大小 、边大小的标准差 和数据的标签数 .

数据集
contact-primary-school 242 12704 127.0 55.3 2.4 0.6 11
contact-high-school 327 7818 55.6 27.1 2.3 0.5 9
house-bills 1494 43047 274.0 282.7 9.5 7.2 2
senate-bills 293 20006 493.4 406.3 7.3 5.5 2
house-committees 1290 340 9.2 7.1 35.2 21.3 2
senate-committees 282 315 19.0 14.7 17.5 6.6 2
walmart-purchases 88860 65979 5.1 26.7 6.7 5.3 11
trivago-clicks 171495 220758 4.0 7.0 4.2 2.0 160

3.4 模型比较和高阶结构

人们经常说,高阶特征对于理解复杂网络的结构和功能很重要。但很少有人能说清哪些类型的高阶特征与哪些网络相关。生成式建模提供了一种比较不同类型的高阶结构的方法。在 DCHSBM 中,此结构由亲和函数 指定。比较每个亲和度函数的似然函数可以表明哪一个最有可能作为基础数据的高阶生成机制。我们使用表 1 中的对称亲和函数和上述节点的标签进行了比较。在这个比较中,我们可以计算亲和函数 的近似 ML(最大似然) 估计并给定它的函数形式。为了进行具体的比较,有必要指定 GN、RP 和 Pairwise 亲和度的函数形式。我们使用以下公式给出: