摘要

图聚类，它以无监督的方式给定节点特征和边连接的集合对图的节点进行聚类，长期以来一直在图学习中进行研究，并且在某些应用中是必不可少的。虽然这项任务很常见，但在实践中会出现更复杂的情况——我们是否可以使用一些图级辅助信息或以弱监督的方式更好地聚类节点，例如，在给定额外标签的情况下识别社交网络中的潜在欺诈用户欺诈社区。这引发了一个有趣的问题，我们将其定义为弱监督图聚类（WSGC）。在本文中，我们首先正式讨论 WSGC 的各种可能设置。在这样的讨论中，我们通过利用图标签和节点特征来研究弱监督图聚类的特定任务，并借助层次图进一步表征不同图之间的连接。为了解决这个任务，我们提出了高斯混合图卷积网络（GMGCN），这是一个简单而有效的框架，用于在由提议的共识损失引导的图标签的监督下学习节点表示，然后通过高斯推断每个节点的类别混合层 (GML)。进行了广泛的实验来测试弱监督图聚类公式的合理性。实验结果表明，在图标签的帮助下，弱监督图聚类方法比传统的图聚类方法有了很大的改进。

1 简介

随着深度图学习的发展，图聚类在社区检测（Jin et al., 2019）、文本聚类（Aggarwal & Zhai, 2012）和其他应用（Yang et al., 2010）方面取得了显着的进步。这些应用程序都假设只有节点/边缘信息和连接是可访问的，以帮助以无监督的方式进行图聚类。然而，更多的图级辅助信息（例如图标签）也可能是可访问的，并且有助于对图中的节点进行聚类。或者说，我们可以使用图的全局标签来帮助提高图聚类的有效性吗？

这个问题很有趣，在现实世界中也很常见。例如，点云分割，如果我们只知道每个点云中包含的对象，而不是训练过程中的所有节点标签，而不是对已知节点的预测，则可以将其重新考虑为点云中节点的聚类。通过监督图学习方法解决的节点标签（Ye et al., 2018; Li et al., 2019）。此外，在社交媒体中，考虑到以图的形式广泛讨论的热点事件，其中用户作为节点参与，用户之间的相互关注关系作为边，思考如何从中挑选出恶意用户是很有趣的。带有这些事件主题标签的用户数量，例如每个主题的真实性（Zhou & Zafarani, 2018; Cao et al., 2018）。实际上，这个问题更像是弱监督方式的图聚类（Zhou，2018），或者称为弱监督图聚类（WSGC），其中可用的训练标签比我们想要拟合的节点标签粗得多.与仅基于节点特征或图结构进行聚类的传统图聚类 (Girvan & Newman, 2002) 不同，WSGC 由图的给定标签信息更好地保证，我们将证明这会密切影响聚类结果。

请注意，WSGC 不同于传统的弱监督学习问题。通常，弱监督学习被认为包括三种类型的弱监督问题：不完全监督、不准确监督和不精确监督（Zhou，2018）。 WSGC 不同于不完全监督，其中训练节点的子集带有标签，而不准确监督则给定节点标签并不总是真实的，因为 WSGC 不包含任何用于训练的节点标签。它也不同于不精确的监督，其作为多实例学习 (MIL) (Carbonneau et al., 2018) 的代表性方法采用袋子的全局标签来识别局部实例的标签。因为 MIL 假设每个实例都是 i.i.d。并且不涉及边缘连接。据我们所知，尽管 WSGC 对于制定一些现实世界的问题非常有用，但还没有关于 WSGC 的研究。因此，将 WSGC 作为一个新的挑战进行研究并为其寻求新的解决方案是非常有趣和重要的。

在本文中，我们正式定义了弱监督图聚类（WSGC），即利用图标签、图结构和节点特征的图聚类任务。为了解决这一特定任务，我们提出了一种基于高斯混合模型（GMM）和图卷积网络（GCN）的新模型，称为高斯混合图卷积网络（GMGCN）。所提出的模型包括一个高斯混合层（GML）和一个新的分层 GAT（hierGAT）来分别更新节点和图形隐藏表示。具体来说，我们设计了一个共识损失，它在训练过程中借助图标签的帮助在改进节点聚类方面发挥着关键作用。最后根据GML的参数进行图聚类。主要贡献如下：

1. 新问题：我们引入了一个新问题，即弱监督图聚类（WSGC），它试图根据图的标签来识别图中的节点，我们对这个问题的变体进行正式讨论以吸引更多的人研究关注这个问题。 2.新的解决方案：我们提出了一种基于GMM和GCN的有效模型GMGCN来解决WSGC。据我们所知，这是第一个通过将 GMM 集成到 GCN 中实现图结构中图聚类的工作。 3.新损失：我们提出了一种共识损失函数，通过“同吸引，相反排斥”的原则来促进模型训练。实验验证了这种共识损失的有效性。

我们在各种合成和现实世界的数据集上验证了 WSGC 相对于传统聚类方法的显着改进。与性能最佳的基线方法相比，GMGCN 在 5 个合成数据集上将归一化互信息（NMI）平均提高了 13%，在 PHEME 社交媒体数据集上提高了 13% 以上，并通过在点云分割数据集上超过 18%。

2 相关作品

图学习。最近，人们对图学习领域越来越感兴趣。在所有现有的工作中，GCN 是最有效的卷积模型之一。一个典型的 GCN 模型是 Gilmer 等人提出的消息传递神经网络（MPNN）。 (Gilmer et al., 2017) 将几种神经网络和图卷积网络方法重新概括为一般的“消息传递”架构。多种 GCN（Bruna 等人，2014；Defferrard 等人，2016；Kipf & Welling，2017；Chang 等人，2020）为 GCN 提供不同的消息传播功能。其中，Graph Attention Networks (GAT) (Velicˇkovic ́ et al., 2017) 首先利用可学习的自注意力层来聚合加权邻居的信息。除了这些方法来获得适当的节点表示之外，还提出了池化策略来整合节点表示上的信息 (Wu et al., 2020)，例如最大/最小池化 (Defferrard et al., 2016)、SortPooling (Zhang et al., ., 2018) 等等。此外，林等人。 (Lin et al., 2017) 提出了一种可学习的注意力池，用于节点表示的加权平均。尽管对节点级和图级图学习任务进行了广泛的研究，但很少有关于 WSGC 的研究。

图聚类。图聚类是一项基本的数据分析任务，旨在将相似的节点归为同一类别。许多现实世界的应用程序都被视为图聚类（Shi & Ma-lik, 2000; Hastings, 2006）。图聚类的主要策略是在节点特征上执行传统的聚类算法，例如 K-means (Jain, 2010) 或 GMM (McLachlan & Basford, 1988)。随着深度学习的巨大成就，越来越多的图聚类研究求助于图学习来学习嵌入，从而捕捉节点特征和结构关系（Wu et al., 2020）。研究人员采用堆叠稀疏自动编码器（Tian 等人，2014 年）、变分自动编码器（Kipf & Welling，2016 年）或自动编码器和 GCN 的组合（Bo 等人，2020 年）来获得用于聚类的图表示。然而，由于缺乏对图标签的关注，这些图聚类方法的性能不如 WSGC 方法。

多实例学习。与 WSGC 具有相似定义的另一个任务是多实例学习 (MIL)。 MIL 是归纳机器学习的一种变体，其中每个学习示例由一个实例包而不是单个特征向量组成（Foulds & Frank，2010）。当获取局部实例注释成本高或不可能，但可以使用包的全局标签时，使用 MIL 来训练使用弱标记数据的分类器。由于它适用于现实世界的问题，它受到了相当多的关注（Andrews 等人，2002a；Cheplygina 等人，2019）。虽然 MIL 从包的标签中学习分类器来对实例进行分类，但它忽略了实例之间的结构信息，因此不适合 WSGC。

高斯混合模型。作为提出的 GMGCN 模型的核心部分，GMM 是高斯分量密度加权和的参数概率密度函数 (McLachlan & Basford, 1988)。它通常用于查找数据样本中的底层集群（Bishop，2006）。通常，GMM 参数是使用迭代期望最大化 (EM) (Moon, 1996) 算法从训练数据中估计的。在本文中，我们将 GMM 集成到 GCN 中以建立 WSGC 的解决方案，并使用随机梯度下降更新 GMM 参数。

点云语义分割。由于 3D 扫描仪的发展，如光探测和测距 (LIDAR)、运动结构转换 (SFM) 技术等，3D 点云的语义分割引起了更多研究人员的关注。点云，PointNet (Qi et al., 2017a) 提出将输入点细分为块网格并单独处理每个这样的块，但考虑到每个点的有限邻域上下文。为了克服这个缺点，许多方法（Engelmann et al., 2017; Ye et al., 2018; Qi et al., 2017b）都建立在 PointNet 之上，并更好地捕捉局部空间结构以及长依赖上下文。最近，一些最新的工作（Qi et al., 2017c; Landrieu & Simonovsky, 2018; Wang et al., 2019）重新考虑将非结构化 3D 点云的语义分割作为对图数据节点的预测，并结合上下文信息和拓扑信息在 3D 点之上。然而，如果点标签未知，这些监督图学习方法不适用于弱监督点云语义分割数据集。

3 符号和问题说明 3.1 符号

我们用 N 个图表示一组图实例为 G = {(G(1),y(1)),...,(G(N),y(N))}，其中 G(n) 指第 n 个图实例和 y(n) ∈ {0, 1, . . . , Cgraph − 1}是Cgraph不同类别对应的图标签。我们用 G(n) = (V(n),E(n)) 表示 sizeM 的第 n 个图实例，其中节点 v(n) ∈Vandedges(v(n),v(n))∈E(n)， byX(n) ={x(n),...,x(n)}∈RMn×d ni ij 1Mn 节点V(n)的特征矩阵，其中d表示节点原始特征的维数，byA( n) ∈{0,1}Mn×Mn 将边 (v(n),v(n)) 与 A(n) 相关联的邻接矩阵。We ij i,j 表示{z(n),..., z(n)}∈{0,1,...,C −1}节点的潜在标签V(n) 其中C1 Mn 节点node 是节点类别的预期数量。此外，如果 G 中的图包含互连，我们用 Ahier ∈ {0,1}N×N 表示图之间链接的邻接矩阵。

3.2 问题陈述

弱监督图聚类（WSGC）问题定义为：给定一组图标签对 G 和节点特征 X，如何推断第 n 个图中第 i 个节点的标签 z(n)，其中 n ∈ {1,...,N} 和 i ∈ {1,...,Mn}？在 WSGC 的定义下，有一些不同的情况可以从问题中扩展为新的任务。