文章导航
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) 是具有社区结构和异构度数序列的图的生成模型。——将其推广到超图
设
我们使用亲和函数
2.2 度估计和亲和参数
在一般随机块模型 (SBM) 及其亲属中有许多推理方法:变分坐标上升、变分置信传播和马尔可夫链蒙特卡罗等。本文通过坐标上升执行近似最大似然推断。将DCSBM最大似然推断与图聚类中流行的模块化目标相结合。坐标上升框架,是块模型推理的期望最大化(EM)算法的近亲。EM算法构建“软”集群,每个节点在每个集群都有一个可能性,取最大可能;坐标上升法生成“硬”集群,其中每个节点恰好属于一个集群。轮廓似然方法(Profile likelihood methods)为最大似然推断提供了一个替代框架,可能是未来研究的方向。
在最大似然框架中,我们通过求解优化问题来学习节点标签的估计
第一项
在最大似然的坐标上升方法中,我们在两个阶段之间交替。在第一阶段,我们假设当前估计
需要解决几个可识别性[6]问题:
- 首先,排列
和 中的组标签不会改变似然值。因此,我们对组标签施加任意顺序。 - 其次,可能的组数
原则上可以大于 中存在的组数。这种情况对应于存在统计上可能但在给定数据实现中为空的组。虽然其他处理方法是可能的,但我们选择忽略空组,将 的数量等于 估计中不同组的数量。 - 不可识别性(unidentifiability)的最终形式与
和 的尺度有关。对于固定的 和 ,我们可以构造 ≠ 和 ≠ 使得 (补充附录 A)。因此,为了确保可识别性,我们必须在 和 上设置一个联合标准化条件。我们选择约束 使得:
其中
公式(9)的用处是,当
首先,对于固定标签向量
其次,以
总的来说,我们可以为数据中每个可能的标签元组估计一个这样的
公式 (11) 也可以直接插入到完全似然最大化问题 (2) 中,消除与
- 我们能够通过推广常见图聚类最大似然超图Louvain算法,以开发快速启发式算法来很好地解决问题 (8) 。
- 在我们的框架中解决问题 (7) 也可以解释为评估固定聚类向量
的轮廓似然性[7],突出了这些方法之间的关系。
我们现在研究推断标签向量
2.3 对称模块度
上一节的结果表明,估计的度参数
我们通过规定
定义函数
我们现在为
其中
对于
目标函数 (14) 与最近提出的多路超图切割问题相似。他们根据分割函数制定超图切割目标,当边缘在两个或多个集群之间分裂时,这些函数将进行惩罚。然后,目标是最小化惩罚的总和,约束条件为为某些节点不得位于同一集群中。我们框架中的对称亲和函数(
表 1. 对称亲和函数。在整个过程中,
亲和函数类型 | 公式 |
---|---|
全有或全无 (AON) | |
分组数量 (GN) | |
相对复数 (RP) | |
节点对 |
![image-20220805172941030](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220805172941030.png)
- 全有或全无(AON) 亲和函数仅区分给定边是否完全包含在单个集群中。这种亲和力函数对于可扩展计算尤其重要,我们将在下面进一步讨论。
- 分组数量 (GN) 亲和性仅取决于边缘中包含的不同组的数量,而与每个组中的事件节点数无关。 GN 亲和函数在应用中经常出现特殊情况。当
时,模块化目标的第一项对应于超边切割惩罚,在科学计算文献中称为“连通性-1(connectivity − 1)”、K-1 度量(the K–1 metric)或边界切割(boundary cut)。它在数据库文献中也被称为扇出(fanout)[9]。相关的外部度数总和惩罚也是 GN 亲和函数的一个特例。 - 相对复数 (RP) 亲和函数仅考虑边缘中表示的最大组的大小与下一个最大组的大小之间的相对差异。这种相当专业的亲和函数特别适用于分组大致平衡的情况,例如,我们在国会委员会的党派关系中发现。
- 节点对亲和函数计算边缘内分组不同的节点对的数量。虽然此亲和函数使用与二元图模型使用相似的信息,但在任何二元随机图和具有节点对亲和函数的 DCHSBM 之间没有立即明显的等价性。
- 还有更多对称的亲和函数;可用于定义亲和力的其他拆分函数见文献52的表三。
![image-20220805175612331](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220805175612331.png)
块模型和模块化度之间的关系最近在文献56中得到了关注。这种思考也适用于我们对上文公式(14)和下文公式(15)的推导。我们在一般的、无约束的亲和函数
2.4 AON 模块度
——全有或全无模块度
建模和计算对AON 亲和函数特别感兴趣。对于相互作用或关系的发生在很大程度上取决于组同质性的系统,这种亲和函数是一种自然选择。
将表 1 中的 AON 亲和函数插入公式 (14), 经过一些代数计算(补充附录 F),得到目标函数:
其中
在这个表达式中,
最近,有研究提出了超图的“严格模块化”的优化目标函数。这种严格的模块化是公式 (15)的一个特例, 通过选择
2.5 超图最大似然鲁汶-HMLL
为了优化模块化目标函数(14)和(15),我们提出了一系列凝聚聚类算法。这些算法通过对节点标签向量
这种启发式可以自然地推广到超图的上。然而,异构超边大小和一般亲和函数的结合使实现变得相当复杂。
在这里,我们提供了一种高度通用的超图最大似然 Louvain (HMLL-hypergraph maximum likelihood Louvain) 算法,用于优化对称模块化目标 (14)。对于 AON 亲和函数的重要案例,简化的目标 (15) 采用了更简单、更快的专用 Louvain 算法,我们在补充附录 G 中对此进行了描述。正如我们在后续实验中所展示的,这种专用算法具有高度可扩展性,并且可以有效地恢复由 AON 亲和函数合理建模的多元结构数据集中的真实集群。
2.6 对称HMLL
- 我们的对称 HMLL 算法的第一阶段对映标准图上的 Louvain:节点从单例集群开始,然后贪婪地移动到相邻的集群,直到无法再增加模块度。
- 普通图 Louvain 的第 2 阶段以保持结构的方式将集群之间的边简化为超节点之间的加权边。然而,在超图的情况下,简单地折叠集群和超边会丢弃有关超边大小和每个超边在集群之间划分方式的重要信息。因此,在我们算法的后续阶段,我们通过移动原始超图中的整个节点集来贪婪地改进目标,而不是贪婪地移动单个节点。这样,在先前迭代中分配给同一集群的一组节点本质上被视为超级节点(supernode)并作为一个单元移动,而不会折叠超图并丢失有关超边结构的所需信息。
我们的整个过程在算法 S1 和 S2 中进行了形式化。算法 S1 依次访问上一次迭代的集群
![image-20220807115313098](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220807115313098.png)
![image-20220807115335490](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220807115335490.png)
算法 S1 依赖于一个函数
因此,虽然节点集群在算法 S1 中也作为一个单元移动,但在这种情况下,有必要在算法的所有阶段对完整的邻接数据
2.7 AON HMLL
当
补充附录G
上一节我们给出了通用对称亲和函数
![image-20220807115717243](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220807115717243.png)
Louvain 步骤本身由算法 2 给出。在每个阶段,我们检查折叠节点
是通过设置
![image-20220807115737671](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220807115737671.png)
值得注意的是,在一般对称HMLL算法 1 中,
![image-20220807115749538](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220807115749538.png)
2.8 集群数
与大多数 Louvain 风格的模块化方法一样,用户无法直接控制 HMLL 返回的集群数量。影响聚类数量的一种方法是手动设置亲和函数
影响集群数量的另一种方法是在社区标签上施加贝叶斯先验。在贝叶斯方法的最简单版本中,假设在对边进行采样之前,每个节点都以相等的概率独立地分配了一个
3 结果
3.1 运行时间
二元(Dyadic)Louvain 算法以在大图中高效而闻名。在这里,我们展示了 AON HMLL 可以在合成数据上实现与图 MLL (GMLL) 相似的性能——这是标准二元 Louvain 算法的一种变体——其中我们返回产生最高二元似然的分辨率参数和分区组合。对于固定数量的节点
图 1 显示了当
根据 ARI 的测量,在较小的实例上,HMLL 在恢复种植集群方面的表现优于 GMLL。对于较大的实例,恢复结果类似。尽管 GMLL 和 HMLL 在本实验中获得了相似的准确性,但它们以不同的方式实现,HMLL 倾向于生成比 GMLL 更多、更小的集群。运行时间几乎没有区别,这表明二元团投影(连通分量扩展)对于准确性和性能都不是必需的。我们观察了参数
![image-20220807120017399](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220807120017399.png)
簇内边缘放置概率为
在这个综合实验中,两种算法的组合实现了最强的恢复结果。除了独立运行每个算法之外,我们还运行了一个两阶段算法,其中使用 GMLL 生成中间分区,然后使用 HMLL 对其进行细化。我们再次强调,这些结果是在具有预先优化的亲和力参数的合成超图上获得的,因此细化策略的有效性可能无法推广到真实数据集。在下面显示的经验数据实验中,我们没有显示细化过程的结果,因为在每种情况下,组合方法的输出分区与二元方法的输出分区基本上无法区分。这可能反映了这样一个事实,即我们没有让算法先验地学习与真实数据标签相关的亲和力参数。进一步研究混合策略的性能将具有相当大的实际意义。
3.2 超图扩展(二元投影)和可检测性阈值
非正式地,当该算法的输出标记
图 2 显示了在一个简单的 DCHSBM 上进行的两个实验,其中有两个大小相等的社区,每个社区有 250 个节点。对亲和力
- 每个节点平均与 5 个 2 节点边和 5 个 3 节点边相关。
2 节点边的一部分
连接同一集群中的节点,而 2 节点边的一部分 连接不同集群中的节点。 3 节点边的一部分
连接同一集群中的节点,而 3 节点边的一部分 连接不同集群中的节点。
![image-20220808172912981](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220808172912981.png)
对于*
这部分看不懂
仅在这个实验中,下面讨论的 GMLL 和 AON HMLL 都在似然目标中使用贝叶斯正则化项
在右侧面板中,我们展示了使用 AON HMLL 的相同实验。虚线
有趣的是,还有
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 |
![image-20220814150922470](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220814150922470.png)
3.4 模型比较和高阶结构
人们经常说,高阶特征对于理解复杂网络的结构和功能很重要。但很少有人能说清哪些类型的高阶特征与哪些网络相关。生成式建模提供了一种比较不同类型的高阶结构的方法。在 DCHSBM 中,此结构由亲和函数
- GN 亲和力函数为超边大小和组数的每个组合分配一个单独的参数。
- RP 亲和性函数为边内最大和第二大组之间的差异超过 k/4 的情况分配一个参数,其中 k 是边的大小。
- Pairwise 亲和性函数将一个参数分配给不同组中的二元对的总数超过这些对的可能数量的一半的情况。
- RP 偏爱两个最常见的标签在表示上大致平衡的超边;
- 而 AON、GN 和 Pairwise 都偏爱具有同质聚类标签的超边。
因为这些亲和函数参数的数量不同,我们通过贝叶斯信息准则[10] (BIC) 对它们进行比较,该标准会惩罚具有比数据支持的更多参数的亲和函数。在计算 BIC 时,我们排除了节点数量
表 3 显示了使用这些亲和函数中的每一个的 DCHSBM 的 BIC。在所有研究数据集中,没有一个亲和函数是首选的,这表明存在不同种类的多元结构。在两个国会委员会数据集中,RP 实现了最佳 BIC,而在其他每个数据集中,促进边缘同质性的三个亲和力之一反而是首选。这三种亲和力之间也有重要的区别。在 house-bills 中,Pairwise 亲和度函数总体上实现了最低的 BIC,而在 walmart-purchas 中,Pairwise 亲和度优于除 GN 亲和度之外的所有功能。这表明仅涉及节点标签的成对比较模型这些情况下可以对数据提供相对强的生成解释。反过来,这表明二元算法在这些二元数据集上的性能至少与其多元算法一样好。正如我们将在下面看到的,在这两个数据集中,与 AON HMLL 返回的聚类相比,二元算法可以返回与真实结果更相关的聚类。
表 3. 在我们的完整研究数据集上使用 AON、GN、RP 和 Pairwise 等亲和函数运行DCHSBM 的 BIC 。表 1 中提供了每个亲和函数的定义。较低的 BIC 表示更合理的模型。在每个数据集中实现最低 BIC 的亲和函数以粗体显示。
数据集 | AON | GN | RP | Parwise | |
---|---|---|---|---|---|
contact-high-school | 2.2003 | 2.1946 | 2.4330 | 2.2003 | ×10 5 |
contact-primary-school | 4.1954 | 4.1646 | 4.3990 | 4.1954 | ×10 5 |
house-committees | 2.7128 | 2.7128 | 2.7119 | 2.7127 | ×10 5 |
senate-committees | 9.7934 | 9.7934 | 9.7736 | 9.7933 | ×10 4 |
house-bills | 9.9719 | 9.9720 | 10.003 | 9.9670 | ×10 6 |
senate-bills | 3.1925 | 3.1926 | 3.2030 | 3.1925 | ×10 6 |
walmart-purchases | 1.0763 | 1.0753 | 1.0806 | 1.0758 | ×10 6 |
trivago-clicks | 1.6854 | 1.6866 | 2.0257 | 1.6960 | ×10 8 |
![image-20220814155026998](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220814155026998.png)
3.5 在关系超图中发现类别
![image-20220814162006124](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220814162006124.png)
图 3 小学和高中数据集的聚类算法比较。对于每个数据集,我们对比了从经典图 Louvain 模块化最大化启发式获得的分区、从 GMLL 获得的分区和通过 AON HMLL 获得的分区。显示的分区是经过 20 轮迭代似然最大化后获得相应目标函数的分区。每个框记录具有推断集群和真实标签的指定组合的代理数量。底行可视化大小为
为了测试 AON HMLL 算法本身,我们首先研究它在小学和高中网络中的行为。表 3 中 BIC 分数的比较表明,GN 可能是对数据最具解释性的模型,但我们改为使用 AON 来利用其可观的计算优势。我们在 AON HMLL 和 AON 参数估计之间执行了 20 次交替,并返回了具有最高 DCHSBM 可能性的分区。我们将结果与两种二元方法进行比较。 Graph Louvain 算法的每个步骤在使用标准 Louvain 算法推断集群和使用的近似最大似然框架估计分辨率参数
图 3 比较了每种算法的性能。
在小学数据集的情况下,我们认为基本事实分区是为每个班级准确分配一名教师的分区。 Graph Louvain 能够找到与给定班级标签具有明确相关性的学生分区,但却会将两个小学班级合并,拆分了几个高中班级(左列,前两行)。GMLL 能够完美地恢复小学生的班级标签,对三个高中生进行错误分类。我们提出的 AON HMLL 能够正确恢复两个数据集中的给定分区。
通过研究推断的亲和函数
3.6 具有大超边的集群恢复
在图 4 中,我们研究了 AON HMLL 在我们的多个研究数据集中恢复真实社区的能力。与这两个接触网络不同,这些数据集中的每一个都包含大小高达 25 个节点的边。我们排除了众议院委员会和参议院委员会,理由是这些数据集是不相关的,这表明 AON 显然不合适。我们将 AON HMLL 与 GMLL 的两个变体进行比较。在非归一化变体中,我们通过将每个
![image-20220814162810200](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220814162810200.png)
图 4. 具有已知聚类的数据中超图 AON MLL(算法 S1)与二元似然 Louvain 的比较。点给出了在分区和参数估计之间进行 20 次交替后获得的最高似然分区的 ARI。最大超边尺寸
结果突出了 AON HMLL 的性能对作为数据生成机制的 AON 亲和函数的相对合理性的强烈依赖性(参见表 3)。在 trivago-clicks 中,AON 亲和函数达到了所有四个候选者中最低的 BIC。因为 AON 是一个更合理的生成机制,所以 AON HMLL 能够找到与提供的数据标签相关的分区比二元变体返回的分区更相关,这并不罕见。另一方面,在沃尔玛购买中,Pairwise 亲和力优于 AON。在这种情况下,AON HMLL 的性能要差得多,并且在 2 核中,甚至返回与提供的标签反相关的集群。随着弱连接节点被移除并且生成的数据变得更密集,HMLL 开始返回相关集群。然而,归一化的 GMLL 变体在恢复数据标签方面至少同样有效。在两个国会法案数据集中,Pairwise 亲和力在众议院实现了低于 AON 的 BIC,在参议院实现了可比的 BIC。与这一发现相呼应的是,二元法在每种情况下都优于 AON HMLL。非标准化的 GMLL 在众议院和参议院的法案中表现最好,而标准化的 GMLL 在沃尔玛采购中更受欢迎。此外,HMLL 是仅在 walmart-purchases 小
在解释这些恢复结果时,重要的是要将它们与社区检测方法的一般局限性和特别是模块度最大化的局限性联系起来。没有对数据结构做出隐含假设的社区检测“最佳算法”,算法与数据集的不匹配会产生误导性结果。即使数据生成过程确实与算法假设相匹配——例如从 SBM 生成的合成数据集——最优算法也可能由于稀疏性而无法检测到种植群落 。贪婪的模块化最大化,包括这里考虑的 Louvain 变体,只能找到可能的许多局部最优值之一,其中一些可能在很大程度上彼此不相关。这些考虑意味着:
- (i)我们不能排除可能在三种算法中的任何一种中获得更高分数的其他局部最优值的存在,以及
- (ii)算法无法恢复接近基本事实的聚类这一事实并不意味着它在其既定目标(即局部似然最大化)中“失败”了。
总体而言,我们的结果表明,当具有 AON 亲和函数的 DCHSBM 假设适用于数据时,AON HMLL 在恢复真实社区方面的表现优于二元方法。在实践中,因为我们通常无法访问基本事实标签,所以假设是否适合数据的问题应该由领域专业知识来告知。
4 讨论
我们提出了一种基于 DCHSBM 的多元数据聚类生成方法。从这个模型中,我们推导出了一个对称的、类似模块化的目标,其中包括 AON 模块化目标作为一个重要的特例。这种推导将超图模块化目标与具体的建模假设联系起来,可以根据领域专业知识进行调整。我们还制定了类似 Louvain 的算法来优化这些目标,在 AON 亲和函数的情况下具有高度可扩展性。将这种启发式嵌入到交替近似最大似然方案中,可以对节点集群和亲和性参数进行自适应估计。我们已经通过实验证明,超图算法与二元算法具有明显不同的可检测性机制。我们还对经验数据进行了实验,发现在建模假设有充分根据的数据集中,超图方法优于二元法。
我们的工作指向了许多进一步研究的方向。这些方向之一是算法。我们在 DCHSBM 中进行推理的贪心坐标上升框架有几个重要的限制。
- 首先,因为我们依赖于一个 NP-hard 优化步骤,所以永远无法保证似然的全局最大化。
- 其次,即使是精确的最大似然本身也被限制为推理范式,因为它使用的信息仅包含在似然图的一小部分中。我们的方法,作为仅当集群大小大致相等时才准确的近似值,也可能会受到估计偏差的影响。
- 第三,由 Louvain 风格算法体现的边缘凝聚方法在适用促进边缘内同质性的亲和函数(那三种)方面受到限制。
替代推理范式可以改善部分或全部这些限制。
- 在最大似然推断的框架内,直接最大化轮廓似然为坐标上升提供了一个有趣的替代方案。尽管所有最大似然方法在优化相同的目标函数方面都是等价的,但算法属性(例如运行时间和陷入不良局部最优值的倾向)可能因不同方法而异。
- 完全贝叶斯处理提供了另一条有希望的途径,尽管它们有时在计算可扩展性方面受到限制。
- 变分置信传播提供了一个有趣的折衷方案,实现了相当大的可扩展性以换取几个近似值。
- 最近的工作在这个方向上取得了进展,但与非均匀超图的可扩展性和行为相关的几个问题仍然存在。具有更一般的亲和力函数的可扩展推理的信念传播方法将具有特别的实际意义。
还有几个重要的理论发展方向。其中之一是 DCHSBM 中的可检测性问题。由于 DCHSBM 比二元 DCSBM 更灵活,因此该模型中的可探测性理论可能要复杂得多。另一个方向涉及扩展到此处讨论的超图模块化目标的二元模块化目标的属性。除了作为与空模型比较的作用和作为 DCSBM 似然性中的一个术语外,二元模性还表达了图上扩散过程的稳定性和定义的离散表面张力的能量图表。这些属性的扩展,或者解释它们为什么不能概括,对理论家和实践者都有帮助。
附注
1 生成vs.判别
帖子:生成方法vs判别方法+生成模型vs判别模型
生成模型:能够随机生成观测数据的模型,可以用来直接对数据建模。
与判别模型区别:生成模型,就是同时考虑了X和Y的随机性,也就是说二者都是随机变量;判别模型,就是只考虑了Y的随机性,而X并不是个随机变量,即使X存在于条件中,但是并没有p(x)这种说法。
生成模型有三个基本用处:一个是概率密度估计,一个是采样,还有就是监督学习,如朴素贝叶斯。
2 超图的两种扩展方式
clique expansion(连通分量扩展)
将超边中所有顶点都连接在一起,比如有3个顶点的超边,扩展成普通图时两两相连就会有3条边。以此类推。连接和n个顶点的超边拓展后有
个边。 同一个超边转换成的边具有跟以前边同样的权重。 star expansion(星形扩展)
在每个超边中加入一个“星星”,连接上其他的点,所以这种方式会在原来的节点上增加额外的节点,也就是有加点的操作,而法一是没有的。加上的点归入一个集合,原来的点归入另一个集合,这个拓展后的普通图是一个二部图(bipartite graph又称作二分图,是图论中的一种特殊模型。)
星图边的权重变成 对应超边 的权重除以超边的度。
3 二元图-dyadic graph
图的dyad:图中两个点和它们之间的所有边构成图的一个“dyad”。
dyadic graph:直接理解就是普通图,其中边表示的是两点之间的二元关系。
![image-20220804115129606](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220804115129606.png)
4 随机块模型SBM
也叫做种植分区模型(planted partition model)
一种图生成模型,英文全称stochastic block model。SBM是一个传统的图生成模型,认为每个节点从属于不同的社区,每个社区之间的节点会以不同的概率相连接,由此生成一张图,这就是它基本的思想。他可以用于社区检测,图聚类,主题建模等任务。
5 坐标上升法
坐标上升法(Coordinate Ascent)每次通过更新函数中的一维,通过多次的迭代以达到优化函数的目的。
6 可识别性
定义: identifiability(可识别性),即如果一个因果量可以通过纯统计量计算得到,则该因果量为可识别的,这意味着我们可以从观测数据中求得因果效应。
一个模型是可识别的,那么其参数跟观察变量的概率分布的映射是一对一的。
在观察性研究中,借助什么样的数据可以推出可靠的因果效应呢?具体来说,假如我们对每个用户有一系列干预前的指标(pre-treatment variables) 𝑋、有干预 𝑇、有观察结果 𝑌
我们能不能推断出 T 对 Y 的因果效应?
这个问题就是因果推断中的可识别性问题。可识别性依赖于几个假设,这些假设通常被称为causal assumption
7 轮廓似然函数
![image-20220804195134038](/2022/08/14/%E7%94%9F%E6%88%90%E5%BC%8F%E8%B6%85%E5%9B%BE%E8%81%9A%E7%B1%BB%EF%BC%9A%E4%BB%8E%E5%9D%97%E6%A8%A1%E5%9E%8B%E5%88%B0%E6%A8%A1%E5%9D%97%E5%8C%96/image-20220804195134038.png)
轮廓似然函数及其应用 Maximum Likelihood, Profile Likelihood, and Penalized Likelihood: A Primer
8 符号滥用
Abuse of notation
在数学中,当作者以一种在形式上并不完全正确但可能有助于简化阐述或提出正确直觉的方式使用数学符号时(同时可能最大限度地减少错误和混淆),就会出现符号滥用。
9 扇入扇出
扇入:是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程序高。
扇出:是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高,需要控制和协调过多的下级模块;但扇出过小(例如总是1)也不好。
10 贝叶斯信息准则 BIC
其中k为模型参数的个数,n为样本的数量,L为似然函数。
模型评估标准:BIC值越低越好。
p和q越大时,参数越多,k越大。所以使k越小,p和q越小,保证模型越好。
L越大,使BIC的值越小,所以似然函数越大越好。