超图聚类论文阅读2:Last-step算法

这篇具有很好参考价值的文章主要介绍了超图聚类论文阅读2:Last-step算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

超图聚类论文阅读2:Last-step算法

《使用超图模块化的社区检测算法》

《Community Detection Algorithm Using Hypergraph Modularity》

COMPLEX NETWORKS 2021, SCI 3区

具体实现源码见HyperNetX库

工作:提出了一种用于超图的社区检测算法。该算法的主要特点是它可以根据一个社区中的顶点与其他社区中的顶点共享超边的频率进行调整以适应各种场景。

动机和贡献

复杂网络中的社区发现——超图社区发现

  • 理论和工具的发展还不够充分,无法在超图情况下直接解决包括聚类在内的大多数问题。

  • 研究者经常创建感兴趣的超图的 2 部图(即,用团替换每个超边)。移动到 2-section 图后,人们显然失去了一些关于尺寸大于 2 的超边的信息,因此人们普遍认为,利用原始超图的知识可以做得更好

相关工作

  • Kumar 等人仍然将问题简化为图,但使用原始超图迭代调整权重以鼓励某些超边包含在某些聚类中但不鼓励其他超边
  • 作者自己在之前提出了图的经典空模型的许多超图扩展,这些扩展可能被真正的超图算法使用

本文贡献:提出了一个能够适应上述各种场景的框架

  • 将图模块化函数的所有扩展推广和统一到超图,并将它们放入一个框架中来实现这一点

  • 不同“切片”的贡献由可以针对给定场景调整的超参数控制(第2节)

  • 提出了两种原型算法来展示框架的潜力,即所谓的概念验证(第 3 节)

  • 引入了一个可能具有独立兴趣的合成随机超图模型,以测试算法在各种场景中的性能(第 4 节)

  • 试验了我们的原型以及该领域的两个主要竞争对手,即 Louvain 和 Kumar 等(第 5 节)

    • 适当调整超参数后,所提出的原型工作得很好
    • 提供了这样的调整可以以无监督的方式进行的证据
  • 揭示更多关于该效果的细节(第 6 节)

模块度函数

我们进一步概括了超图模块化函数,使我们能够以不同的方式评估对模块化函数的各种贡献

图模块度

G = (V, E)、n = |V|、度:degG(v)、社区A的体积

  • 模块化函数有利于图 G 的顶点集的分区,其中大部分边完全落在parts(通常称为簇)内
  • benchmark是用Chung-Lu 随机图模型生成的图具有完全遵循 G 中的度序列的随机图上相连的情况

给定分区A:边贡献+度税
q G ( A ) = ∑ A i ∈ A e G ( A i ) ∣ E ∣ − ∑ A i ∈ A ( vol ⁡ G ( A i ) vol ⁡ G ( V ) ) 2 q_G(\mathbf{A})=\sum_{A_i \in \mathbf{A}} \frac{e_G\left(A_i\right)}{|E|}-\sum_{A_i \in \mathbf{A}}\left(\frac{\operatorname{vol}_G\left(A_i\right)}{\operatorname{vol}_G(V)}\right)^2 qG(A)=AiAEeG(Ai)AiA(volG(V)volG(Ai))2

  • qG(A) ≤ 1
  • 一个分区的话,值为0;一个点是一个分区的话,值小于0
  • 找到最大模块度的分区——接近1
  • 如果 q*(G) 接近于零(这是平凡的下界),则不存在社区结构

超图模块度

可以推广成二部图进行计算,每条边的权重为w(e)/(|e| − 1)

  • 这种选择可确保创建的图的度分布与原始超图相同
  • 它也很好地将 H 上的自然随机游走转换为相应 H[2] 上的随机游走
  • 此过程会创建多重图

H = (V, E)、degH(v)、volH(A)

超图模块化函数的选择并不是唯一的。这取决于人们有多强烈地相信超边是其某些顶点落入一个社区的指标。即超边对社区的贡献

  1. 超边的所有顶点都必须属于其中一个部分
  2. 如果超边超过 50% 的顶点属于分区,则超边对这个分区有贡献
  3. 超边可能有助于对应于最大部分顶点属于的分区

majority-based modularity

Bin(d, p) 表示具有参数 d 和 p 的二项式随机变量
q H m ( A ) = ∑ A i ∈ A e H m ( A i ) ∣ E ∣ − ∑ d ≥ 2 ∣ E d ∣ ∣ E ∣ ∑ A i ∈ A P ( Bin ⁡ ( d , vol ⁡ H ( A i ) vol ⁡ H ( V ) ) > d 2 ) q_H^m(\mathbf{A})=\sum_{A_i \in \mathbf{A}} \frac{e_H^m\left(A_i\right)}{|E|}-\sum_{d \geq 2} \frac{\left|E_d\right|}{|E|} \sum_{A_i \in \mathbf{A}} \mathrm{P}\left(\operatorname{Bin}\left(d, \frac{\operatorname{vol}_H\left(A_i\right)}{\operatorname{vol}_H(V)}\right)>\frac{d}{2}\right) qHm(A)=AiAEeHm(Ai)d2EEdAiAP(Bin(d,volH(V)volH(Ai))>2d)
strict-based modularity
q H s ( A ) = ∑ A i ∈ A e H s ( A i ) ∣ E ∣ − ∑ d ≥ 2 ∣ E d ∣ ∣ E ∣ ∑ A i ∈ A ( vol ⁡ H ( A i ) vol ⁡ H ( V ) ) d = ∑ A i ∈ A e H s ( A i ) ∣ E ∣ − ∑ d ≥ 2 ∣ E d ∣ ∣ E ∣ ∑ A i ∈ A P ( Bin ⁡ ( d , vol ⁡ H ( A i ) vol ⁡ H ( V ) ) = d ) \begin{aligned} q_H^s(\mathbf{A}) & =\sum_{A_i \in \mathbf{A}} \frac{e_H^s\left(A_i\right)}{|E|}-\sum_{d \geq 2} \frac{\left|E_d\right|}{|E|} \sum_{A_i \in \mathbf{A}}\left(\frac{\operatorname{vol}_H\left(A_i\right)}{\operatorname{vol}_H(V)}\right)^d \\ & =\sum_{A_i \in \mathbf{A}} \frac{e_H^s\left(A_i\right)}{|E|}-\sum_{d \geq 2} \frac{\left|E_d\right|}{|E|} \sum_{A_i \in \mathbf{A}} \mathrm{P}\left(\operatorname{Bin}\left(d, \frac{\operatorname{vol}_H\left(A_i\right)}{\operatorname{vol}_H(V)}\right)=d\right) \end{aligned} qHs(A)=AiAEeHs(Ai)d2EEdAiA(volH(V)volH(Ai))d=AiAEeHs(Ai)d2EEdAiAP(Bin(d,volH(V)volH(Ai))=d)
——emH(Ai) 计算大多数顶点属于部分 Ai 的超边数,而在 (3) 中,esH(Ai) 计算所有顶点都属于部分 Ai 的超边数

统一和泛化

独立处理来自大小为 d 的超边对模块化函数的贡献,分别考虑超边内包含在社区的节点恰好为c的情况

上面的多数模块度可以写成:
q H m ( A ) = ∑ A i ∈ A ∑ d ≥ 2 ∑ c = ⌊ d / 2 ⌋ + 1 d ( e H d , c ( A i ) ∣ E ∣ − ∣ E d ∣ ∣ E ∣ ⋅ P ( Bin ⁡ ( d , vol ⁡ H ( A i ) vol ⁡ H ( V ) ) = c ) ) q_H^m(\mathbf{A})=\sum_{A_i \in \mathbf{A}} \sum_{d \geq 2} \sum_{c=\lfloor d / 2\rfloor+1}^d\left(\frac{e_H^{d, c}\left(A_i\right)}{|E|}-\frac{\left|E_d\right|}{|E|} \cdot \mathrm{P}\left(\operatorname{Bin}\left(d, \frac{\operatorname{vol}_H\left(A_i\right)}{\operatorname{vol}_H(V)}\right)=c\right)\right) qHm(A)=AiAd2c=d/2+1d(EeHd,c(Ai)EEdP(Bin(d,volH(V)volH(Ai))=c))
ed,c H (Ai) 是Ai 中恰好有 c 个成员的大小为 d 的超边的数量

可以写成:
q H m ( A ) = ∑ d ≥ 2 ∑ c = ⌊ d / 2 ⌋ + 1 d q H c , d ( A ) q_H^m(\mathbf{A})=\sum_{d \geq 2} \sum_{c=\lfloor d / 2\rfloor+1}^d q_H^{c, d}(\mathbf{A}) qHm(A)=d2c=d/2+1dqHc,d(A)
其中定义一个“切片”:
q H c , d ( A ) = 1 ∣ E ∣ ∑ A i ∈ A ( e H d , c ( A i ) − ∣ E d ∣ ⋅ P ( Bin ⁡ ( d , vol ⁡ ( A i ) vol ⁡ ( V ) ) = c ) ) q_H^{c, d}(\mathbf{A})=\frac{1}{|E|} \sum_{A_i \in \mathbf{A}}\left(e_H^{d, c}\left(A_i\right)-\left|E_d\right| \cdot \mathrm{P}\left(\operatorname{Bin}\left(d, \frac{\operatorname{vol}\left(A_i\right)}{\operatorname{vol}(V)}\right)=c\right)\right) qHc,d(A)=E1AiA(eHd,c(Ai)EdP(Bin(d,vol(V)vol(Ai))=c))
严格模块度可写成:
q H s ( A ) = ∑ d ≥ 2 q H d , d ( A ) q_H^s(\mathbf{A})=\sum_{d \geq 2} q_H^{d, d}(\mathbf{A}) qHs(A)=d2qHd,d(A)
——多数超图模块度中每个“切片”的权重相等,而对于基于严格的定义模块度,仅考虑 c = d 的切片

新模块化函数由超参数 wc,d ∈ [0, 1] (d ≥ 2, [d/2] + 1 ≤ c ≤ d) 控制

给出广义超图模块度统一定义:
q H ( A ) = ∑ d ≥ 2 ∑ c = ⌊ d / 2 ⌋ + 1 d w c , d q H c , d ( A ) q_H(\mathbf{A})=\sum_{d \geq 2} \sum_{c=\lfloor d / 2\rfloor+1}^d w_{c, d} q_H^{c, d}(\mathbf{A}) qH(A)=d2c=d/2+1dwc,dqHc,d(A)
α ∈ [ 0 , ∞ ) \alpha \in[0, \infty) α[0,), and ρ min ⁡ , ρ max ⁡ ∈ ( 0.5 , 1 ] \rho_{\min }, \rho_{\max } \in(0.5,1] ρmin,ρmax(0.5,1] $\rho_{\min } \leq \rho_{\max } $
w c , d = { ( c / d ) α  if  ⌈ d ρ min ⁡ ⌉ ≤ c ≤ ⌈ d ρ max ⁡ ⌉ 0  otherwise  w_{c, d}= \begin{cases}(c / d)^\alpha & \text { if }\left\lceil d \rho_{\min }\right\rceil \leq c \leq\left\lceil d \rho_{\max }\right\rceil \\ 0 & \text { otherwise }\end{cases} wc,d={(c/d)α0 if dρmincdρmax otherwise 
该定义为我们提供了更大的灵活性,并允许对某些切片的估值高于其他切片。

  • 参数 ρmin 和 ρmax 分别与超边的最小和最大“纯度”假设相关,并取决于网络的同质性水平
  • 参数 α 控制不同“纯度”级别的贡献超边之间的相对信息量之间的平滑过渡

在相应地调整超参数之后,广义模块度 可以用于两种极端情况(基于多数和基于严格)以及介于两者之间的任何情况。

此外,广义模块度 可以很好地近似对应的 2 部分图 H[2] 的图模块性。

算法

经典

  1. Louvain:通过考虑其 2 部分(加权)图 H[2] 将问题简化为图,然后尝试找到最大化图模块性函数的分区

    它是一种层次聚类算法,试图优化模块化功能(模块化优化阶段),将社区合并为单个顶点(社区聚合阶段),然后递归地对压缩图执行模块化聚类,直到无法增加模块化为止。

    • 所有的聚类算法在本质上都是启发式的,只旨在找到“足够好”的分区,而不希望找到最好的分区。
    • Louvain 是一种随机算法,在模块化优化阶段发生之前随机排序所有顶点。不幸的是,这意味着该算法不稳定,并且其结果在独立运行之间可能会有很大差异。
    • 为了解决这个问题,可以改用图的集成聚类算法(ECG)。该算法以 Louvain 算法和共识聚类的概念为基础,具有良好的稳定性
  2. Kumar:以下改进通常会在几个合成和真实示例中给出比原始 Louvain 算法更好的结果。

    该算法并不是真正基于超图的,而应该被视为由原始超图引导的基于图的方法的改进

    • 首先在原始超图H的基础上构建一个保度加权图G
    • 将Louvain算法应用于G,试图最大化图模块函数
    • 重新访问超图 H 并根据它们对所获得部分之间的同质性的度量对超边进行仔细的重新加权。
    • 重复这些步骤直到收敛。

LS and HA

传统方法总结:所有基于图模块化优化的成功算法(包括上文提到的 Louvain、ECG 和 Kumar 等)都是以相同的方式开始的。顶点最初自己是一个簇,若模块度增加则将顶点的集群更改为其邻居之一。

——超图中此方法的问题:那么只改变一个顶点的集群可能不会对模块化函数产生积极影响,除非存在小尺寸边。

算法:使用普通图模块化函数 qG(A) 进行“从地面提升过程”,再切换到超图对应函数 qH(A)

——两种, (HA) 尽快切换到超图、 (LS) 停留在图上的时间更长

  1. HA(混合算法)
    1. 通过在从 H 构建的保度图 G 上使用 qG(A) 运行 ECG 来形成小而紧密的团块。修剪低于 70%(投票数)阈值的边,并将连通分量保留为初始团块。
    2. 如果 qH(A) 提高,则合并团块(以随机顺序)。重复直到无法再改进为止。
    3. 一次将一个顶点(以随机顺序)移动到相邻的簇,如果它提高了 qH则保留。重复直到收敛。
  2. LS(最后一步)
    1. 运行 Kumar 算法
    2. 只执行上面的最后一步(步骤 3.)

给出三个参数传入两种算法中:HA(α, ρmin, ρmax) 和 LS(α, ρmin, ρmax)

合成随机超图模型

经典随机图模型:

  • 众所周知和广泛使用的 LFR 基准图

  • 作者自己开发的ABCD

提出了一个受经典随机块模型启发的模型

模型特征:所提出的模型旨在简单,但它试图捕捉这样一个事实,即许多以超图表示的现实世界网络表现出不同程度的同质性或缺乏同质性。它为我们提供了一个工具来测试我们的算法在各种场景下的性能。一个好的算法应该能够以无监督的方式适应任何场景。

实验

设置合适的参数将对算法效果产生积极影响

超图聚类论文阅读2:Last-step算法,超图聚类,算法,聚类,论文阅读

结论和未来方向

  1. 提出了两种原型算法并做了一些简单的实验来展示它们的潜力

    • 展示了我们的原型算法工作得很好,但只有在对超参数进行适当调整后才能工作
    • 初步实验表明,这种调整可以以无人监督的方式完成,但细节需要修复,并且需要解决过拟合问题
  2. 提出了两种方法来解决任何基于超图模块化函数的算法的初始阶段问题

    1. 将 2-section 图的顶点嵌入到几何空间中,使用具有较大 k 值的经典 k-means 算法来找到初始分区
    2. Kumar 等人提出的 Hyperedge 重新加权方案似乎效果很好,可以很容易地合并到我们的框架中。我们的目标是建立一个灵活的框架,该框架可以模仿 Louvain、ECG、Kumar 等人以及介于两者之间的任何东西,但通过超图模块化功能提供的机会得到额外增强。

方向:文章来源地址https://www.toymoban.com/news/detail-699379.html

  • 该算法必须是可扩展的,超图模块化功能的更新可以快速完成,但需要正确设计/使用专用数据结构和算法。我们目前使用 Julia 语言实现这样的代码。
  • 除了对大型合成超图进行实验之外,还计划对以超图表示的真实网络进行实验

到了这里,关于超图聚类论文阅读2:Last-step算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【论文阅读】通过对比聚类分配的深度多视图聚类

    原文链接 对于大多数现有的深度MVC方法, 探索多视图的不变表示 仍然是一个棘手的问题。在本文中,提出了一种 跨视图对比学习(CVCL)方法 ,该方法学习视图不变表示,并通过比较多个视图之间的聚类分配来产生聚类结果。 具体来说,首先在预训练阶段使用深度自编码器提

    2024年02月21日
    浏览(46)
  • 【论文阅读】深度多视图聚类的自监督判别特征学习

    文章链接 聚类结构不明确 的某些视图所带来的负面影响,导致多视图聚类性能较差,所以本文提出SDMVC。 深度编码器用来独立的学习每个视图 ;为了利用互补信息, 将所有视图的嵌入特征串联起来形成全局特征 ,可以克服某些视图聚类结构不清晰的负面影响。以 自监督的

    2024年02月02日
    浏览(42)
  • 论文阅读1--A Survey on Incomplete Multi-view Clustering(不完全多视图聚类的调查)阅读笔记

    目录 写在前面(知识补充) 0.Abstract 1.Introduction 2. FUNDAMENTALS AND PRELIMINARY CONCEPTS 3. MATRIX FACTORIZATION BASED IMC(基于矩阵分解的IMC) 4. KERNEL LEARNING BASED IMC(基于内核学习的IMC) 5.GRAPH LEARNING BASED IMC(基于图学习的IMC) 6.DEEP LEARNING BASED IMC(基于深度学习的IMC) 7. EXPERIMENTS(实验部分)

    2024年02月05日
    浏览(56)
  • 强化学习论文阅读(二)SAC算法

    原文传递:SAC算法原文 作者指出深度强化学习样本效率低下的原因是:策略学习,TRPO、PPO、A3C每次策略更新都需要收集样本。学习有效的策略需要的步骤和样本数量伴随着任务的复杂性呈现增加的趋势。Off-Policy为了重复使用过去产生的经验值,但是在传统的策略公式当中不

    2024年02月06日
    浏览(44)
  • 对比学习论文阅读:CoCLR算法笔记

    标题:Self-supervised Co-training for Video Representation Learning 会议:NIPS2020 论文地址:https://dl.acm.org/doi/abs/10.5555/3495724.3496201 官方代码:https://www.robots.ox.ac.uk/~vgg/research/CoCLR/ 作者单位:牛津大学 本文的研究目标是纯视觉的自监督视频表征学习。我们做出了以下贡献:①我们研究了在

    2024年02月03日
    浏览(59)
  • 图像生成论文阅读:GLIDE算法笔记

    标题:GLIDE: Towards Photorealistic Image Generation and Editing with Text-Guided Diffusion Models 会议:ICML2022 论文地址:https://proceedings.mlr.press/v162/nichol22a.html 官方代码:https://github.com/openai/glide-text2im 作者单位:OpenAI 扩散模型最近已被证明可以生成高质量的合成图像,特别是在与引导技术结合

    2024年02月02日
    浏览(44)
  • 【论文阅读】StyleganV1 算法理解

    听过Stylegan的人都觉得他很强!目前stylegan已经发展到第三代v3了,但是为了搞清思想,我还是从v1开始了解,以下是我个人的一些理解。 传统GAN采用端对端的输入输出,可以尽可能使用训练集数据的信息,但是会出现两个问题。 仅保持一种输入,纵使网络有再强的能力,也可

    2024年02月12日
    浏览(50)
  • 论文阅读--用于小物体检测的增强算法

    Title: Augmentation for small object detection Abstract: In the recent years, object detection has experienced impressive progress. Despite these improvements, there is still a significant gap in the performance between the detection of small and large objects. We analyze the current state-of-the-art model, Mask-RCNN, on a challenging dataset, MS COCO. We sh

    2024年02月15日
    浏览(54)
  • 论文阅读笔记 | 三维目标检测——PV-RCNN++算法

    如有错误,恳请指出。 paper:《PV-RCNN++: Point-Voxel Feature Set Abstraction With Local Vector Representation for 3D Object Detection》(2022 IJCV) 做点云检测的肯定知道了,这又是Shaoshuai Shi大佬的另外一篇文章,Shaoshuai Shi大佬的主页介绍:https://shishaoshuai

    2023年04月08日
    浏览(85)
  • 【论文阅读】互连网络的负载平衡路由算法 (RLB & RLBth)

    前言 Oblivious Load Balancing 不经意路由负载平衡 1. oblivious routing 不经意/无关路由的背景知识 1. oblivious routing, adaptive routing minimal/non-minimal routing algorithms 2. Balancing a 1-Dimensional ring: RLB and RLBth 一维 ring 的 RLB and RLBth 1. Motivation of Balancing load 平衡负载的动机 2. 一维 ring 的 RLB and RLB

    2024年04月25日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包