如何做美食的视频网站,肯德基的网站建设,互联网行业前沿资讯,wordpress内容导航https://arxiv.org/pdf/2201.04066.pdf 社群检测是网络科学中一个基础而重要的问题#xff0c;但基于图神经网络的社群检测算法为数不多#xff0c;其中无监督算法几乎是空白。 本文通过将高阶模块化信息与网络特征融合#xff0c;首次提出了基于变异图自动编码器重构的社群…https://arxiv.org/pdf/2201.04066.pdf 社群检测是网络科学中一个基础而重要的问题但基于图神经网络的社群检测算法为数不多其中无监督算法几乎是空白。 本文通过将高阶模块化信息与网络特征融合首次提出了基于变异图自动编码器重构的社群检测 VGAER并给出了其非概率版本。它们不需要任何先验信息。 我们根据社群检测任务精心设计了相应的输入特征、解码器和下游任务这些设计简洁、自然、性能良好在我们的设计下NMI 值提高了 59.1% - 56.59%。 基于广泛的数据集和先进方法的一系列实验VGAER 取得了优异的性能并以更简单的设计显示出强大的竞争力和潜力。最后我们报告了算法收敛性分析和 t-SNE 可视化结果这些结果清晰地描述了 VGAER 的稳定性能和强大的网络模块化能力。我们的代码见 https://github.com/qcydm/VGAER。
Introduction 作为描绘现实世界最重要的物理工具之一网络数据如今正逐渐向大规模、复杂化和模块化方向发展。例如社交平台网络Wang 等人2015 年、基因工程中的蛋白质相互作用网络Pizzuti 和 Rombo2014 年、交通网络Von Ferber 等人2009 年等。不仅节点之间存在复杂的相互作用网络还会因为这种相互作用和节点的贡献而形成不同的群落。从拓扑学角度看群落可以理解为内部节点连接相对紧密外部节点连接相对稀疏。识别这种局部结构对于理解复杂系统和发现知识至关重要Krishnamurthy 和 Wang2000 年。 上述任务就是社区检测。关于社群检测的研究有很多。特别是近年来随着图神经网络的发展2019年首次提出了基于图神经网络的社区检测方法Chen、Li和Bruna2017Shchur和G¨unnemann2019包括超视图方法基于非回溯理论Chen、Li和Bruna2017、基于马尔可夫随机场Jin等2019和已知的无监督方法基于复杂回归重构的方法GUCD(2020)He等2021a以及基于负样本对比学习和自表达性的SE21a。2019以及已知的无监督方法基于复杂回归重构的方法 GUCD(2020) He 等人2021a和基于负样本对比学习和自我表达的 SEComm(2021) Bandyopadhyay 和 Peter2021。然而大数据系统网络社区的先验信息如标签有时很稀缺这也给上述半监督方法和几乎罕见的无监督方法带来了巨大挑战。因此为这一领域提出更好的无监督方法就显得尤为重要。 另一方面经过大量全面的文献调查我们发现目前所有的图神经网络群落检测Chen, Li, and Bruna 2017Shchur and G¨unnemann 2019Jin et al. 2019) (He et al. 2021a)甚至所有聚类方法如 MGAE (Wang et al. 2017)、ARGA (Pan et al. 2018)、AGC (Zhang et al. 2019)、SDCN (Bo et al. 2020) 和 AGE (Cui et al. 2020) 等。这些方法只注重保留网络结构和节点特征A X以及不同正则化方法或模型设计为网络嵌入带来的聚类增益 与以往方法根本不同的是我们首次在基于图神经网络的社群检测中提出了一种基于模块化和网络结构B A X的无监督联合优化方法 VGAER该方法具有严格的模块化理论基础更适合社群检测网络结构A被隐式捕获通过消息传递阶段无需显式重构。 我们还注意到Yang 在 2016 年利用这一模块化理论提出了一种基于自动编码器的非线性重构方法记为 DNRYang et al. 2016。2018 年之后在这项工作的基础上又有人提出了多种整合不同网络特征的自动编码器重构方法Cao et al. 2018Bha- tia and Rani 2018Cao, Jin, and Dang 2018。然而这些方法往往需要额外的操作而且捕捉网络特征的能力有限因此当针对未知群落结构的网络时这种 DNR 方法的 Q 值非常低。我们将在第 4 节中演示这一现象。总之与这些基于自动编码器的群落检测方法相比我们的 VGAER 不仅具有更好的性能而且还扩展到了基于自动编码器的方法尚未覆盖的变分模型中。 最后我们横向比较了 VGAER 和先进的基于无监督 GNN 重构的 GUCDHe et al. 2021a的检测效果充分显示了 VGAER 即使与最先进、最复杂的方法相比也具有很强的竞争力以及进一步发展的潜力如更复杂的架构和设计。我们的创新贡献和见解如下 本文提出了一种基于图变分推理的全新社群检测方法并给出了更精确的非概率版本。并在广泛的数据集和参数算法上获得了卓越的性能改进。 - 首次提出了基于模块化和网络结构的联合优化框架。VGAER 性能的提高得益于我们模型的非线性模块化重构和邻域拉普拉斯平滑这可以部分缓解单一模块化最大化导致的极端退化问题Good、De Montjoye 和 Clauset2010 年和恢复限制Fortunato 和 Barthelemy2007 年。 - VGAER 不仅能处理群落检测任务还具有强大的生成能力这意味着 VGAER 还能在不同前提下根据所学分布灵活生成嵌入。我们期待 VGAER 未来能在社区节点预测、社区嵌入、个人隐私保护等方面发挥作用。我们将在附录中为这些机会描绘更广阔的图景。
Methodology
The model 考虑一个图 GVE我们可以根据公式 2 得出模块化矩阵 B。如果 G 有节点特征 X那么 作为一个深度生成模型我们首先为 VGAER 设计了一个推理模型 其中 q (zi | B, A) 是基于高斯族的节点 i 真实后验分布的变分近似值 然后我们使用两个图神经网络 µ GCNµ(B, A) 和 log σ GCNσ (B, A) 作为编码器来确定节点 i 的均值向量 µ 和标准偏差向量 σ 其中W0 和 W1 分别代表第一层和第二层的权重矩阵。W0 由 GCNσ 和 GCNµ 共享。 是对称重规范化邻接矩阵。tanh 是激活函数。我们必须指出使用 tanh 重新设置 ReLU 的必要性因为模块化矩阵 B 包含大量 0 元素如果使用 ReLU梯度将无法有效更新。 我们还可以堆叠多个编码器让 VGAER 完全学习平均值和标准偏差向量真实分布从而提高其准确性。这只需要前一个编码器的输出作为下一个编码器的输入。 在深度生成阶段我们特别设计了一个基于交叉熵的点积解码器来重建模态分布。考虑 p(Bij | zi, zj ) 的条件分布其中 Bij 是重构条目zi 来自重参数化技巧。我们将 p(Bij | zi, zj ) 离散化为两部分p(Bij bij | zi, zj ) 和 p(Bij ! bij | zi, zj ) 。同时利用类似于 VGAE 的重新加权技术Kipf 和 Welling2016 年我们用 σ(bij ) 和 (1-σ(bij )) 对这两部分重新加权 其中 是一个 sigmoid 函数与下式相同。理解公式 14 后重新加权项的含义会更加清晰。p(B | Z) 的计算公式如下 Optimization 我们首先给出由最大化目标函数导出的变分下界 L(φ, θ) 如下 其中B 是 G 的模块化集(φ, θ) ∈ {W0, W1, W2} 是参数空间并取高斯先验P(Z) 。那么优化任务就是 变分下界包含两个项。前一项是重建损失后一项是衡量两个分布相似度的 KL 指数。现在我们考虑之前的具体形式如下 将公式 9 代入对数项即可得到 我们也可以从交叉熵的角度来理解上述公式。式 (14) 构造了条目 bij 的真实分布 σ(bij ) 与点乘重建分布 之间的负交叉熵。最大化这个项等同于最小化两个分布之间的差异即最小化重建损失。
Non-probabilistic version 我们还给出了一种非概率群落检测模型 GAER只使用一个 GCN 作为编码器 下游任务是 这个损失函数在实验中表现良好。至于优化我们建议在快速群落检测任务中使用相应的 F-norm 损失它使用两个矩阵之间的欧氏距离δ {W0, W1} 是参数空间。
