基于多通道图卷积网络的节点聚类

孙艳丰， 杜鹏飞

(1.北京工业大学信息学部， 北京 100124； 2.北京工业大学多媒体与智能软件技术北京市重点实验室， 北京 100124)

聚类是数据分析的一项基本任务，将样本按照相似性关系分到不同的类别中[1]. 最近，由于深度网络所展现出的强大的数据表示学习能力，应用深度网络来解决聚类问题受到人们的关注. 目前，一些深度聚类算法已经成功地在各种实际中进行应用，例如文本聚类[2]、图像聚类[3-4]等. 挖掘数据原始特征空间中的属性信息以获得有判别力的数据表示是深度聚类中的一个关键步骤，例如：Hinton等[5]通过自动编码器(auto-encoder,AE)网络驱动表征学习；Xie等[6]提出了深度编码聚类(deep embedded clustering，DEC)方法，将原始数据空间经过参数化非线性映射到低维特征空间，在低维特征空间优化聚类目标来学习节点表示；Guo等[7]提出了改进的通过保持局部结构进行聚类的网络，该网络引入了重构损失、融合聚类损失和AE的重构损失，从而学习到具有局部结构约束的特征. 然而，这些模型只是针对结构化的数据学习原始节点属性信息，在处理非结构化的图关系数据聚类时表现不佳.

针对图结构数据的聚类问题，最近的研究工作集中于学习图拓扑结构的编码表示，将图拓扑结构与原始节点属性更好地结合. 新兴的图卷积网络(graph convolutional network,GCN)[8]给这一工作带来了巨大的突破. GCN基于图的拓扑结构和节点属性信息，通过聚合来自相邻节点的特征迭代更新节点编码. 在此基础上，Kipf 等[9]提出了图自动编码器(graph auto-encoder，GAE)和变分图自动编码器(variational graph auto-encoder，VGAE)，GAE利用GCN作为编码器获得节点的表示，VGAE使学习到的表示符合高斯先验分布；Fatemi等[10]提出了一种利用高阶图卷积自适应地捕获全局结构信息来学习节点表示的方法；Wang等[11]使用图注意力融合网络作为编码器来融合图结构信息和节点属性；Pan等[12]进一步提出了一种对抗性正则化图自动编码器(adversarially regularized graph auto-encoder，ARGA)用于学习潜在的节点表示；Bo等[13]提出了深度结构化聚类网络(structural deep clustering network，SDCN)，利用深度AE和GCN分别学习节点属性信息和图结构信息表示，并通过自监督机制将它们集成到一个统一的框架中. Peng等[14]提出了注意力驱动的图聚类网络(attention-driven graph clustering network，AGCN)，将图结构信息和节点属性信息通过注意力机制进行融合以获得更利于聚类的节点表示. 现有的方法都是从原始图结构和节点特征中学习优质的嵌入表示，然而，原始的图结构关系由于数据噪声或度量的不准确可能导致关系描述不精确. 另外，有研究表明，GCN在从图拓扑信息和节点属性信息中学习嵌入表示时表现出来的性能并不是特别令人满意[15]，因此，如何获得更准确的嵌入表示是一个关键问题.

针对以上提出的不足之处，本文提出一种深度聚类网络，即基于多通道图卷积网络(multi-channel graph convolutional network, McGCN)的节点聚类.

1 McGCN的节点聚类模型

1.1 符号定义及任务说明

首先介绍一些符号及概念，属性图可以表示为G={V,E,X},其中：V是节点集合；E是边集合；X∈Rn×m是节点的属性矩阵，n表示节点数，m表示特征的维数.图的邻接矩阵表示为A∈Rn×n，如果Vi和Vj之间有边，则Aij=1，否则为0.给定一个图G和聚类数k，属性图聚类的目的是把图G中的节点划分到k个不相交的簇中.任务说明如图1所示，黄色和蓝色分别表示2种类别的节点，聚类模型根据拓扑信息和特征信息将它们分到2个簇中.

图1 属性图聚类示例Fig.1 Example of attributed graph clustering

1.2 整体框架

对于图数据集，本文把原始的拓扑图结构称为拓扑图，把基于节点特征相似度通过K-近邻(K-nearest neighbor，KNN)算法构建的图结构称为特征图.然后，使用AE提取节点特征的数据表示，使用GCN从拓扑图和特征图中提取图的数据表示，以便在不同的空间学习嵌入表示.最后，通过一个自适应融合模块将3个通道得到的节点编码进行融合.此外，采用了自监督机制和编码之间的差异性约束来监督训练过程，模型整体框架如图2所示.

图2 多通道图卷积聚类网络结构Fig.2 Structure of multi-channel graph convolution clustering network

1.2.1 节点特征的编码模块

不考虑节点之间的连接关系，只考虑节点的特征，将节点特征嵌入到低维空间有很多方法，如去噪自动编码器(denoising auto-encoder，DAE)、稀疏自动编码器(sparse auto-encoder, SAE)、变分自动编码器(variational auto-encoder, VAE)等.本文使用最基本的AE，其主要由2个部分组成，即将输入映射到中间层表示的编码器以及将中间层映射到输出的解码器，通过最小化原始特征与重构特征之间的重构损失来学习编码表示.它的编码、解码和重构损失公式分别可以表示为

(1)

(2)

(3)

1.2.2 图结构的编码模块

GAE的目标是根据节点特征和图邻接关系学习图的低维节点嵌入.近年来，GCN在处理图数据上表现出来的性能得到了广泛的认可，基本思想是根据邻接关系聚合邻居节点的特征信息，通过堆叠多层的图网络学习更深层次的表示.给定一个节点特征矩阵X和邻接矩阵A，GCN通过A和X生成新的节点表示，第l层输出可以表示为

(4)

对于图数据，原始图关系可能存在误差，使得通过原始拓扑图和节点特征得到的嵌入表示并不是令人满意的，因此，使用节点之间的特征相似度构建特征图，拓扑图和特征图同时被用来提取图数据的嵌入表示.这种方法可更充分地从特征空间中挖掘可靠信息.另外，为了使算法能够适应非图数据，采用不同K值下KNN算法生成的邻接关系来表示拓扑图和特征图.

1.2.3 融合模块

如何融合这些来自不同通道的节点编码是一个挑战，常用的方法有加权求和、拼接和注意力机制等.为了充分融合由AE和GCN得到的嵌入表示，采用了一种基于注意力的动态融合机制，使得上述3个通道得到的节点表示充分交互.具体的图示如图2所示，首先将来自3个通道的嵌入表示(Zae，Zfg，Ztg)两两加权求和进行初步融合，得到3个新的嵌入表示(Zae-fg，Zae-tg，Zfg-tg)，融合规则用公式表示为

Zae-fg=α·Zae+(1-α)·Zfg
Zae-tg=β·Zae+(1-β)·Ztg
Zfg-tg=γ·Zfg+(1-γ)·Ztg

(5)

式中α、β、γ表示融合的超参数.之后，对Zae-fg、Zae-tg、Zfg-tg应用注意力机制以实现自适应融合，通过全连接层挖掘不同表示之间的关系，使用tanh(·)激活函数，并且进行softmax归一化，将得到的每个嵌入表示系数与对应的嵌入表示加权求和，得到融合之后的嵌入表示.融合规则的公式为

Ztemp=[Zae-fg‖Zae-tg‖Zfg-tg]

(6)

ω=W2(tanh(W1·Ztemp+b))

(7)

(8)

式中：Ztemp∈Rn×3×d表示把待融合的嵌入表示(Zae-fg，Zae-tg，Zfg-tg)拼接到一起；W1、W2均为全连接层的权重；b为偏置；ω∈Rn×3×1表示嵌入表示的融合系数；θ∈Rn×3×1为对系数归一化的结果.由此可以得到最终的融合表示，将融合后的表示通过softmax函数得到n个样本属于k个簇的概率分布Z∈Rn×k，这一过程用公式表述为

Z=softmax(θ1·Zae-fg+θ2·Zae-tg+θ3·Zfg-tg)

(9)

对网络训练后，可以通过Z得到预测的簇标签，公式为

yi=arg maxzi

(10)

式中：yi表示第i个样本预测的簇标签；zi表示Z的第i个样本.

由于特征空间的图结构是通过KNN算法从原始节点属性X生成的，为了充分挖掘特征空间的信息，应训练编码器在节点属性空间和特征图空间学习到有差异的嵌入表示，同时也约束节点属性空间和拓扑图空间的嵌入表示有差异性.为此，本文使用希尔伯特- 施密特独立性准则(Hilbert-Schmidt independence criterion，HSIC)进行约束.HSIC是一种基于核的独立性度量方法，主要功能是衡量2个变量的分布差异，其公式可以描述为

LHSIC(Zae,Zfg)=(n-1)-2tr(RKaeRKfg)

(11)

LHSIC(Zae,Ztg)=(n-1)-2tr(RKaeRKtg)

(12)

1.2.4 自监督模块

获得融合的嵌入表示后，借鉴文献[16]中的策略，对融合后的嵌入表示增加约束,以便更好地实现聚类任务,这也成为现在许多深度聚类方法中实现聚类的最常用策略[17].其详细过程如下：首先，使用Student-t分布作为核来度量由AE学习到的嵌入表示中第i个样本和第j个聚类质心之间的相似性，计算公式为

(13)

式中：qij表示样本zae,i分配到聚类中心μj的概率；zae,i表示AE学习到的嵌入表示Zae的第i个样本；μj是通过对Zae进行K-means计算得到的聚类中心；α表示自由度，是一个超参数，本文实验中设置为1.对每个样本进行计算，得到所有样本分配分布，称之为聚类软分配分布Q.

为了增加聚类的内聚力，使Q的数据表示更接近聚类中心，求得Q的归一化分布P为

(14)

最后，为了使融合后的分布与融合前的分布相一致，在目标分布P的协助下通过优化融合后的嵌入表示分布Z与AE学习到的嵌入表示分布Q之间的KL(Kullback-Leibler)散度达到这一目的，在此使用了2个约束项

(15)

(16)

式中LKL(PQ)、LKL(PZ)分别表示聚类软分配分布Q和融合后嵌入表示分布Z与归一化分布P之间的KL散度.

通过最小化式(15)(16)可以使融合后的分布Z和融合前的分布Q很好地对齐，由于P是通过Q生成的，而P又反过来监督Q的更新，整个过程中没有人为的引导，因此，称为自监督方式.P、Q和Z之间的约束正则项如图2中红色虚线标注所示.

本文通过这一监督方法把AE和GCN整合到一个网络中，实现端到端的训练.在对网络进行训练之后，通过融合后的表示分布Z可以直接得到预测聚类结果，最终，整个网络的损失函数设计为

L=λ1·LR+λ2·LKL(PQae)+λ3·LKL(PZ)+
λ4·LHSIC(Zae,Zfg)+λ5·LHSIC(Zae,Ztg)

(17)

式中：LR表示AE的重构损失；LHSIC(Zae，Zfg)、LHSIC(Zae，Ztg)分别表示对节点属性与特征图和拓扑图编码得到的嵌入表示之间的差异性损失.

整个模型的算法步骤如下.

2 实验

2.1 实验数据

本文在6个常用的基准数据集上进行了实验，包括1个图像数据集USPS、1个人类活动识别记录数据集HHAR、1个文本数据集Reuters和3个图数据集ACM、DBLP、CiteSeer，数据集的简要描述如表1所示.

表1 数据集描述

USPS数据集包括9 298个灰度手写数字图像，共10个类别(即0～9).

HHAR数据集包含智能手表的10 299条传感器记录. 样本被划分为6类人类活动(骑自行车、坐、站、走、上楼梯和下楼梯).

Reuters数据集包含大约81万篇英语新闻故事，并按类别进行标记. 使用公司/工业、政府/社会、市场和经济作为标签.

ACM数据集是来自ACM数字图书馆的一个论文网络数据集，其中边表示同一作者撰写. 特征是关键词的词袋表示. 样本按照研究领域分成3类(数据库、无线通信、数据挖掘).

DBLP数据集是一个作者网络数据集. 节点表示作者，边表示作者合作完成的论文. 作者分为4个领域：数据库、数据挖掘、机器学习和信息检索.

CiteSeer数据集是一个引文网络数据集，包含每个文档的稀疏词汇特征向量包和文档之间的引文链接列表. 标签包含6个领域：代理、人工智能、数据库、信息检索、机器语言和人机交互.

2.2 对比方法

本文将提出的方法与8种方法进行了对比，其中前3种是基于AE的非图数据聚类方法，后5种是基于GCN的图数据聚类方法.

1) AE方法：对AE从原始数据中学习到的嵌入表示执行K-means聚类.

2) DEC方法：在上述AE方法基础上加入约束项，将编码器学习嵌入表示和聚类分配两部分联合后进行优化，不再把两部分割裂开，从而提高聚类.

3) IDEC方法：在DEC上增加了一个自编码器的重构损失以更好地学习嵌入表示，提高聚类效果.

4) GAE方法：结合GCN和AE设计，用于学习数据表示.

5) VGAE方法：在GAE的基础上，从原始数据中学习到一个分布，从这个分布中采样一组数据作为嵌入表示进行聚类.

6) DAEGC方法：使用GAT网络来学习嵌入表示，并生成目标分布，使其指导嵌入表示进行更新.

7) SDCN方法：通过AE学习节点特征表示，并通过GCN学习图结构表示，把这两部分的嵌入表示融合，进行聚类任务.

8) AGCN方法：在SDCN的基础上，在两部分嵌入表示融合时使用了注意力机制，得到更利于聚类的节点表示.

9) McGCN方法：即本文提出的方法.

2.3 聚类结果

本文的方法和8种对比方法在6个基准数据集上的实验结果如表2所示. 表中：ACC表示聚类结果的准确度；NMI表示聚类结果中正确聚类信息的数量；ARI表示类别划分的重叠程度；F1是模型准确率和召回率的调和平均值.

根据表中数据可以观察到：本文方法在6个数据集的比较中大部分指标都获得了最好的聚类性能. 精度提升显著的原因有3个方面：首先，文中的方法增加了一个新的图结构，提供了更丰富的信息；其次，加入差异性约束模块后显著地增加了节点表示的多样性，使其从不同角度学习到有区别的嵌入表示；最后，基于注意力机制融合模块，自适应地融合了来自各个通道的嵌入表示，充分地利用了每个通道中的信息. 在ACM、DBLP数据集中，本文提出的方法性能改进不明显. 通过对模型算法及实验结果进行分析，认为这个数据集的拓扑图与特征图结构比较一致，增加特征图结构并不能有效地提高聚类精度.

2.4 消融实验

针对模型中的差异性约束HSIC，本文进行了消融实验来检验它的作用，实验结果如表3所示. 表中：McGCN表示本文提出的具有HSIC约束的模型；McGCN-HSIC表示去掉HSIC约束的模型. 可以发现，拥有HSIC约束的要明显优于没有HSIC的模型. 这一观察结果表明，HSIC约束能够约束2个通道中的编码器，使其学习不同的嵌入表示，从而利用更全面的信息来提高网络的聚类性能.

表3 HSIC约束对模型的影响

2.5 训练过程分析

通过实验对McGCN的训练过程进行了分析，并与之前的SDCN方法做比较，实验结果见图3.

图3 正确率与训练次数的关系Fig.3 Relationship between accuracy and training times

在Reuters和HHAR的训练过程中存在一些波动，分析原因是3个通道学习到的嵌入表示差异性较大且没有一个具有主导性的嵌入表示，导致在自适应融合时权重分配多样化，进而表现出正确率波动. 但是，随着训练的进行，最终的聚类结果都趋于稳定.

3 结论

1) 本文提出的McGCN方法基于AE和GCN在原始节点特征空间、拓扑图空间和特征图空间进行嵌入表示的学习，并且通过一个基于注意力机制的融合模块将节点编码融合，应用Student-t分布得到样本的软分配分布，通过自监督的方式优化软分配分布与目标分布之间的差异，执行端到端的训练.

2) 在常用的基准数据集上对提出的方法进行评估，结果表明该方法有效地提高了聚类精度.

3) 虽然本文方法已经取得了较好的性能，但由于图结构编码采用的是GCN，它本质上是平等地聚合邻居节点信息，没有更好地结合节点的结构关系属性，存在一定局限性，未来将探索更有效的图结构编码方式.