超图聚类论文阅读1:Kumar算法

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

超图聚类论文阅读1:Kumar算法

《超图中模块化的新度量:有效聚类的理论见解和启示》

《A New Measure of Modularity in Hypergraphs: Theoretical Insights and Implications for Effective Clustering》

COMPLEX NETWORKS 2020, SCI 3区

具体实现源码见HyperNetX库

工作:

  1. 针对超图聚类问题推广模块度最大化框架
  2. 引入了一个超图空模型,它与无向图的配置模型完全对应。
  3. 推导出一个保留超图节点度序列的邻接矩阵缩减

成果:

  1. 使用 Louvain 方法最大化由此产生的模块化函数,已知在图实践中效果很好
  2. 在几个真实世界的数据集上展示了我们的方法的有效性

简介

先前工作

  • 注意力限制在 k-均匀超图上,其中所有超边具有相同的固定大小。

    提出合适的超图拉普拉斯算子来扩展一般超图的谱聚类框架——隐含了图扩展的思想

  • 模块度最大化是图上聚类的另一种方法,它提供了一个标准来衡量模块化函数中的集群质量

    经典方法为louvain算法

  • 团扩展问题:会丢失编码在超边结构中的关键信息。也不会保留超图的节点度——这是模块度最大化方法基于的零模型所必需的

  • 有多种切割超边的方法。根据切割不同侧节点的比例和分配,聚类将发生变化。需要考虑超边权重

本文贡献

  1. 在超图上定义了一个空模型(可以保持超图节点度信息),并使用上述定义了一个模块化函数,可以使用 Louvain 方法将其最大化。
  2. 提出了一种迭代超边重新加权过程,该过程利用来自超图结构的信息和超边切割的平衡。
  3. 在几个真实世界的数据集上凭经验评估了生成的算法,证明了其相对于竞争基线的有效性和效率。

背景知识

  1. 超图——关联矩阵、团扩展
  2. 模块度

超图模块度

节点的采样概率与其参与的超边的数量(或在加权情况下,总权重)成正比
P i j h y p = d ( i ) × d ( j ) ∑ v ∈ V d ( v ) P_{i j}^{h y p}=\frac{d(i) \times d(j)}{\sum_{v \in V} d(v)} Pijhyp=vVd(v)d(i)×d(j)

  • 在进行团扩展时,相应图中节点的度数与它在图中的度数不同原始超图

对于每个超边 e,节点度被多算了一个因子 (δ(e) − 1)。因此,我们可以通过将每个 w(e) 缩小一个因子 (δ(e) − 1) 来纠正它。这导致以下更正的邻接矩阵:
A h y p = H W ( D e − I ) − 1 H T A^{h y p}=H W\left(D_e-I\right)^{-1} H^T Ahyp=HW(DeI)1HT
我们可以使用这种保留节点度数的缩减,将对角线归零,以实现方程式中的空模型。

超图模块度的表达式:
Q h y p = 1 2 m ∑ i j [ A i j h y p − P i j h y p ] δ ( g i , g j ) Q^{h y p}=\frac{1}{2 m} \sum_{i j}\left[A_{i j}^{h y p}-P_{i j}^{h y p}\right] \delta\left(g_i, g_j\right) Qhyp=2m1ij[AijhypPijhyp]δ(gi,gj)
与任何加权图一样,此函数的范围是 [−1, 1]。当超边中没有一对节点属于同一集群时,我们将得到 Qhyp = −1,而当属于同一超边的任何两个节点始终属于同一集群时,我们将得到 Qhyp = 1。 Qhyp = 0,对于任何一对节点 i 和 j,同时包含 i 和 j 的超边数等于包含 i 和 j 的随机连线超边数,由空模型给出。

迭代超边重新加权

问题:最小切割算法会支持尽可能不平衡的切割

思路:我们希望在簇中保留不平衡的超边,并切割更平衡的超边——可以通过增加获得不平衡切割的超边的权重,并减少获得更平衡切割的超边的权重来完成。

超边被一分为二,两边节点数分别为k1、k2:
t = ( 1 k 1 + 1 k 2 ) × δ ( e ) t=\left(\frac{1}{k_1}+\frac{1}{k_2}\right) \times \delta(e) t=(k11+k21)×δ(e)

超图聚类论文阅读1:Kumar算法,超图聚类,算法,聚类,论文阅读

k 1 = k 2 = δ ( e ) / 2 k1=k2=\delta(e)/2 k1=k2=δ(e)/2时,t取最小值4,推广上式:
w ′ ( e ) = 1 m ∑ i = 1 c 1 k i + 1 [ δ ( e ) + c ] w^{\prime}(e)=\frac{1}{m} \sum_{i=1}^c \frac{1}{k_i+1}[\delta(e)+c] w(e)=m1i=1cki+11[δ(e)+c]
——+1 和 +c 项都被添加用于平滑,以解决任何 ki 为零的情况。我们除以 m 来归一化权重

令 wt(e) 为超边 e 在第 t 次迭代中的权重,w’(e) 为在给定迭代中计算的权重,则权重更新规则可写为:
w t + 1 ( e ) = α w t ( e ) + ( 1 − α ) w ′ ( e ) w_{t+1}(e)=\alpha w_t(e)+(1-\alpha) w^{\prime}(e) wt+1(e)=αwt(e)+(1α)w(e)

示例

初始的切分很不均匀,有1:4、1:2、2:3等切分,改进后,不均匀的切割被去除——h1 和 h3 中的单个节点最初分配给另一个集群,已被拉回它们各自的(更大的)集群。

超图聚类论文阅读1:Kumar算法,超图聚类,算法,聚类,论文阅读

实验

度量指标

  • 使用平均 F1 度量兰德指数RI来评估具有真实类别标签的真实世界数据的聚类性能

几种用作对比的方法

  1. 团扩展+louvain

  2. 超图谱聚类

  3. hMETIS 和 PaToH

数据集

  • MovieLens:联合导演
  • Cora 和 Citeseer:论文共同作者
  • TwitterFootball:足球俱乐部
  • Arnetminer:共引论文

结果文章来源地址https://www.toymoban.com/news/detail-699447.html

  • 在所有数据集上显示最佳平均 F1 分数、在除一个数据集外的所有数据集上显示最佳兰德指数分数
  • 在所有数据集和两种实验设置上都优于各自的团扩展方法
  • f分析得出碎片边增加,这可能对应于更平衡的切割

结论

  • 考虑了超图上的模块化最大化问题。在提出超图的模块化函数时,我们推导出了一个节点度保持图缩减和一个超图空模型
  • 为了进一步细化聚类,我们提出了一种超边重新加权过程,可以平衡聚类方法引起的切割
  • 迭代重新加权模块化最大化 (IRMM)在数据集上表现出不错的性能

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

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

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

相关文章

  • 【论文阅读】深度多视图聚类的自监督判别特征学习

    文章链接 聚类结构不明确 的某些视图所带来的负面影响,导致多视图聚类性能较差,所以本文提出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)
  • 《基于改进YOLOv5的无人机图像检测算法》论文阅读

    原文链接:UAV Recognition and Tracking Method Based on YOLOv5 | IEEE Conference Publication | IEEE Xplore 《基于改进YOLOv5的无人机图像检测算法》论文阅读        基于深度学习的目标检测算法通常对传统目标检测效果较好,但对小目标的检测精度较低。针对该问题,该文通过对无人机采集图像

    2024年02月14日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包