摘要： 針對(duì)自動(dòng)編碼器僅對(duì)單個(gè)數(shù)據(jù)所包含的內(nèi)容信息進(jìn)行特征提取， 忽略了數(shù)據(jù)之間結(jié)構(gòu)信息的問(wèn)題， 提出一種基于異構(gòu)融合和判別損失的深度圖聚類網(wǎng)絡(luò). 首先， 將兩個(gè)自動(dòng)編碼器獲取的異質(zhì)信息進(jìn)行融合， 解決了采用單一自動(dòng)編碼器提取特征時(shí)的信息丟失問(wèn)題; 其次， 在聚類訓(xùn)練模塊基于類內(nèi)分布一致性設(shè)計(jì)判別損失函數(shù)， 使模型可以端到端地訓(xùn)練， 避免了兩階段訓(xùn)練方法中出現(xiàn)特征提取與聚類算法提前假設(shè)不匹配的情況； 最后， 在6個(gè)常用數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)并驗(yàn)證了該方法的有效性. 實(shí)驗(yàn)結(jié)果表明， 與現(xiàn)有的大多數(shù)深度圖聚類模型相比， 該方法在非圖數(shù)據(jù)集和圖數(shù)據(jù)集上的聚類性能有明顯提升.

關(guān)鍵詞： 圖聚類； 深度學(xué)習(xí)； 判別損失； 異構(gòu)融合

中圖分類號(hào)： TP391 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)： 1671-5489（2023）04-0853-10

Graph Embedding Clustering Based on Heterogeneous Fusion and Discriminant Loss

YAO Bo， WANG Weiwei

（School of Mathematics and Statistics， Xidian University， Xi’an 710126， China）

Abstract： [JP+1]Aiming at the problem that autoencoder" only extracted features from" the content information contained in a single data， ignoring the structure information of data， we proposed a deep graph clustering network based on heterogeneous fusion and discriminant loss. Firstly， the heterogeneous[JP］information obtained by two autoencoders was fused， and the problem of information loss was solved when a single autoencoder was used to extract features. Secondly， the discriminant loss function was designed in the clustering training module based on the consistency of distribution within the same cluster， so that the model could be trained end-to-end， and avoiding the mismatch between the feature extraction and the assumptions of the clustering algorithm in the two-stage training methods. Finally， experiments were carried out on six commonly used datasets to verify the effectiveness of the proposed method. The experimental results show that compared with most existing deep graph clustering models， the proposed method" significantly improves the clustering performance on both non-graph and graph datasets.

Keywords： graph clustering; deep learning; discriminant loss; heterogeneous fusion

聚類是機(jī)器學(xué)習(xí)領(lǐng)域中的一項(xiàng)基本無(wú)監(jiān)督任務(wù)， 其基本思想是利用不同的相似度衡量方法將數(shù)據(jù)劃分為不同的類別. 經(jīng)典的聚類方法如基于劃分方法的K均值（K-means）聚類 ［1］、 基于密度的聚類方法DBSCAN（density-based spatial clustering of applications with noise）［2］、 譜聚類（spectral clustering， SC）［3］、 高斯混合（Gaussian mixed model， GMM）聚類［4］、 非負(fù)矩陣分解（non-negative matrix factorization， NMF）聚類［5］都是直接對(duì)數(shù)據(jù)進(jìn)行操作， 這類方法適用于低維數(shù)據(jù). 隨著信息科技的發(fā)展， 現(xiàn)實(shí)生活中信息量巨增， 數(shù)據(jù)的維度越來(lái)越高. 高維數(shù)據(jù)常伴隨信息冗余以及噪聲， 這不僅會(huì)導(dǎo)致算法的計(jì)算復(fù)雜度上升， 還會(huì)影響聚類精度［6]. 上述方法不再適用于此類數(shù)據(jù)， 目前普遍的解決方法是首先利用數(shù)據(jù)降維方法將原始數(shù)據(jù)映射到低維特征空間， 得到原始數(shù)據(jù)的特征表示， 然后對(duì)所提取的特征進(jìn)行聚類， 但一些高維數(shù)據(jù)之間復(fù)雜的非線性結(jié)構(gòu)仍是聚類算法要解決的難題.

由于深度神經(jīng)網(wǎng)絡(luò)具有強(qiáng)大的非線性映射能力， 因此基于深度神經(jīng)網(wǎng)絡(luò)的聚類算法［7-9］已在圖像分類、 人臉識(shí)別等技術(shù)領(lǐng)域廣泛應(yīng)用. 深度嵌入聚類（deep embedding clustering， DEC）［7］及其變體改進(jìn)深度嵌入聚類（improved deep embedded clustering， IDEC） ［8］、 基于非對(duì)稱殘差自動(dòng)編碼器（autoencoder， AE）的深度嵌入聚類［9］利用卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural networks， CNN）［6］提取數(shù)據(jù)的隱特征， 卷積操作保留了包含在圖像、 自然語(yǔ)言等歐氏數(shù)據(jù)中的關(guān)鍵信息， 極大提升了聚類精度， 但這些方法作用于單個(gè)數(shù)據(jù)， 并未考慮數(shù)據(jù)之間的關(guān)聯(lián)性. 實(shí)際應(yīng)用中的數(shù)據(jù)常存在一定的聯(lián)系， 例如引文網(wǎng)絡(luò)［10］、 社交網(wǎng)絡(luò)［11］等， 具有同一作者的兩篇論文、 互為好友的人群之間應(yīng)該具有較強(qiáng)的聯(lián)系. 這些數(shù)據(jù)為非歐氏數(shù)據(jù)， 可以被表示為圖（graph）. 在這種數(shù)據(jù)中， 不僅包含數(shù)據(jù)本身的內(nèi)容信息， 還包含數(shù)據(jù)與數(shù)據(jù)之間的某種關(guān)聯(lián)度， 具體表現(xiàn)為邊的連接. 因此， 深度聚類方法［7-9］存在一定的局限性： 首先， 這類方法在提取數(shù)據(jù)特征時(shí)并未考慮數(shù)據(jù)與數(shù)據(jù)之間的聯(lián)系， 將會(huì)導(dǎo)致得到的特征表示不包含數(shù)據(jù)的結(jié)構(gòu)信息， 使信息不全面從而導(dǎo)致聚類性能欠佳; 其次， 這類方法普遍適用于歐氏數(shù)據(jù)， 只能在二維空間進(jìn)行特征提取， 而現(xiàn)實(shí)生活中的數(shù)據(jù)常以三維的形式出現(xiàn)； 最后， 這類方法一般[KG*8]作用于單個(gè)數(shù)據(jù)， 增加了算法的運(yùn)行時(shí)間和計(jì)算損耗.

為克服上述局限性， 研究者們提出了作用在圖上的深度聚類方法［12-14］. 圖卷積網(wǎng)絡(luò)（graph convolutional network， GCN）［12］是經(jīng)典的深度圖聚類方法之一， 它通過(guò)作用于節(jié)點(diǎn)屬性矩陣和鄰接矩陣捕獲節(jié)點(diǎn)之間的結(jié)構(gòu)信息， 得到具有結(jié)構(gòu)信息的特征表示. 通過(guò)最小化交叉熵對(duì)特征表示進(jìn)行監(jiān)督， 以保證特征表示的有效性. 最終對(duì)得到的特征表示進(jìn)行聚類. 但該方法仍有不足： 1） 其為一種兩階段法， 首先提取原始數(shù)據(jù)的特征表示， 然后對(duì)特征表示進(jìn)行聚類得到類別分配， 這樣的兩階段法不能保證得到的特征表示與所用的聚類方法具有較高的適配度， 導(dǎo)致聚類性能次優(yōu); 2） 圖卷積網(wǎng)絡(luò)主要利用中心節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)得到特征表示， 忽略了節(jié)點(diǎn)本身的內(nèi)容信息， 同樣會(huì)導(dǎo)致信息丟失從而影響聚類性能; 3） 在指導(dǎo)網(wǎng)絡(luò)訓(xùn)練階段使用的交叉熵?fù)p失函數(shù)中需要用到數(shù)據(jù)的真實(shí)標(biāo)簽， 而在實(shí)際應(yīng)用中獲取真實(shí)標(biāo)簽需要耗費(fèi)巨大的人力、 物力. 針對(duì)上述問(wèn)題， 結(jié)構(gòu)深度聚類網(wǎng)絡(luò)（structural deep clustering network， SDCN）［13］將來(lái)自兩個(gè)自動(dòng)編碼器的特征表示進(jìn)行融合， 得到一個(gè)融合特征表示， 并設(shè)計(jì)了一個(gè)對(duì)偶自監(jiān)督模塊為網(wǎng)絡(luò)訓(xùn)練提供指導(dǎo). 它將特征提取與網(wǎng)絡(luò)訓(xùn)練整合在一個(gè)框架中， 通過(guò)端到端地訓(xùn)練得到類別分布， 有效提升了聚類性能. 但該網(wǎng)絡(luò)框架舍棄了解碼器和重構(gòu)損失， 可能導(dǎo)致空間特征扭曲， 使特征表示不具有代表性.

基于上述問(wèn)題， 結(jié)合GCN和SDCN， 本文設(shè)計(jì)一個(gè)端到端訓(xùn)練的深度圖嵌入聚類網(wǎng)絡(luò)， 從類內(nèi)和類間兩個(gè)角度設(shè)計(jì)損失函數(shù)， 使同一類特征之間的距離小， 不同類特征之間的距離大. 此外， 本文在SDCN融合特征的基礎(chǔ)上引入一個(gè)圖解碼器， 對(duì)原始數(shù)據(jù)的內(nèi)容信息以及結(jié)構(gòu)信息進(jìn)行重構(gòu)， 通過(guò)最小化重構(gòu)損失保證融合特征表示中包含高質(zhì)量的結(jié)構(gòu)信息， 從而更利于聚類. 在6個(gè)公開(kāi)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明， 本文方法具有較高的泛化能力和聚類性能.

1 預(yù)備知識(shí)

1.1 圖卷積網(wǎng)絡(luò)

GCN是作用在圖數(shù)據(jù)上的圖表征提取方法， 網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示. GCN由兩層圖卷積層組成， 非線性激活函數(shù)為ReLU， 首先使用圖卷積網(wǎng)絡(luò)對(duì)圖中的節(jié)點(diǎn)進(jìn)行卷積操作， 得到每個(gè)節(jié)點(diǎn)特征表示組成的特征矩陣：

3.3 方法性能對(duì)比

將本文方法與其他聚類算法性能進(jìn)行比較， 從而驗(yàn)證本文方法的聚類性能. 為驗(yàn)證本文方法的泛化性能， 選取圖數(shù)據(jù)集和非圖數(shù)據(jù)集兩種類型的數(shù)據(jù)集， 表2列出了不同方法在圖數(shù)據(jù)集上的聚類結(jié)果. 為避免出現(xiàn)個(gè)別特殊結(jié)果， 表2中的結(jié)果為實(shí)驗(yàn)運(yùn)行5次后取得的平均值. 表3列出了不同方法在非圖數(shù)據(jù)集上的聚類結(jié)果. 對(duì)于對(duì)比方法K-means， 本文運(yùn)行5次選取平均值， 其他的對(duì)比方法結(jié)果參考文獻(xiàn)［13］和文獻(xiàn)［27］.

由表2和表3可見(jiàn)， 本文方法在大部分?jǐn)?shù)據(jù)集上聚類性能優(yōu)于其他方法. 對(duì)于圖數(shù)據(jù)集ACM，DBLP和Citeseer， 相比于SDCN， 本文方法的聚類性能指標(biāo)ACC分別提升了2.30%，3.57%，5.52%； 對(duì)于非圖數(shù)據(jù)集HHAR，USPS和REUT， 本文方法的聚類性能指標(biāo)ACC分別提升了2.04%，0.13%，0.55%. 可見(jiàn)， 本文方法更適用于圖數(shù)據(jù)集. 其原因可能有兩個(gè)： 1） 人為構(gòu)造非圖數(shù)據(jù)集的拓?fù)浣Y(jié)構(gòu)導(dǎo)致結(jié)構(gòu)信息不明確； 2） 非圖數(shù)據(jù)集的樣本數(shù)是圖數(shù)據(jù)集樣本數(shù)的3倍， 樣本數(shù)目太多導(dǎo)致網(wǎng)絡(luò)訓(xùn)練困難. 實(shí)驗(yàn)結(jié)果表明， 本文方法可有效增強(qiáng)特征表示的可判別性， 提升聚類性能.

3.4 消融實(shí)驗(yàn)

為測(cè)試本文方法中各模塊的重要性， 設(shè)計(jì)一個(gè)消融實(shí)驗(yàn)進(jìn)行驗(yàn)證. 從整個(gè)模型中剔除相應(yīng)的損失函數(shù)， 觀察聚類性能的變化， 聚類性能下降越明顯， 表示該模塊在聚類過(guò)程中的促進(jìn)作用越大. 本文的整體損失函數(shù)包括5個(gè)， 重構(gòu)損失Lrec3個(gè)： 圖特征重構(gòu)損失、 圖結(jié)構(gòu)重構(gòu)損失和卷積重構(gòu)損失； 聚類損失2個(gè)： 基于類內(nèi)數(shù)據(jù)相互靠近的L1和基于類間數(shù)據(jù)相互遠(yuǎn)離的L2. 消融實(shí)驗(yàn)結(jié)果列于表4， 其中“×”表示剔除該損失函數(shù).

由表4可見(jiàn)， 當(dāng)從完整的方法中剔除任何一個(gè)損失函數(shù)時(shí)， 聚類性能都會(huì)下降， 證明了每個(gè)模塊對(duì)于聚類過(guò)程的促進(jìn)作用. 剔除圖特征重構(gòu)或圖結(jié)構(gòu)重構(gòu)時(shí)， 聚類性能下降程度相當(dāng)， 說(shuō)明特征與結(jié)構(gòu)的重要性大致相同. 而當(dāng)剔除卷積重構(gòu)時(shí)， 聚類性能下降程度較大， 說(shuō)明卷積自動(dòng)編碼器提取的數(shù)據(jù)本身的信息非常重要， 證明了異質(zhì)信息的交互可有效提升聚類性能.

3.5 收斂性分析

下面設(shè)計(jì)兩個(gè)實(shí)驗(yàn)驗(yàn)證本文方法的收斂性： 首先， 在數(shù)據(jù)集ACM上觀察樣本分布圖， 隨著迭代次數(shù)的增加， 樣本分布是否趨于穩(wěn)定； 其次， 根據(jù)迭代次數(shù)的增加觀察聚類精度是否趨于平穩(wěn). 實(shí)驗(yàn)結(jié)果分別如圖4和圖5所示. 由圖4和圖5可見(jiàn)， 隨著迭代次數(shù)的增加， 樣本逐漸分為3類， 并在迭代300次后， 類別分布趨于穩(wěn)定； 同時(shí)， 3個(gè)指標(biāo)精度隨著迭代次數(shù)的增加逐漸上升并趨于平緩. 從而本文方法的收斂性得以證明.

綜上所述， 為解決圖數(shù)據(jù)的聚類問(wèn)題， 本文提出了一個(gè)基于異構(gòu)融合和判別損失的圖嵌入聚類網(wǎng)絡(luò). 首先對(duì)不同結(jié)構(gòu)自動(dòng)編碼器提取的數(shù)據(jù)信息進(jìn)行線性融合； 然后基于同一類分布一致性和不同類分布差異性設(shè)計(jì)損失函數(shù)， 利用反向傳播訓(xùn)練網(wǎng)絡(luò)參數(shù)； 最后利用K-means算法作用于特征表示得到最終的聚類結(jié)果. 在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明， 本文方法可有效提升聚類性能， 其中對(duì)圖數(shù)據(jù)集的聚類提升效果明顯.

參考文獻(xiàn)

［1］LLOYD S P. Least Squares Quantization in PCM ［J］. IEEE Transactions on Information Theory， 1982， 28（2）： 129-137.

［2］KNEGEL H P， KROGER P， SANDER J， et al. Density-Based Clustering ［J］. Wiley Interdisciplinary Reviews： Data Mining and Knowledge Discovery， 2011， 1（3）： 231-240.

［3］NG A Y， JORDAN M I， WEISS Y. On Spectral Clustering： Analysis and an Algorithm ［C］//Advances in Neural Information Processing Systems. Cambridge： MIT Press， 2001： 849-856.

［4］BISHOP C M. Pattern Recognition and Machine Learning" ［M］. Berlin： Springer-Verlag， 2006： 1-758.

［5］CICHOCKI A， MRUP M， SMARAGDIS P， et al. Advances in Nonnegative Matrix and Tensor Factorization ［J］. Computational Intelligence and Neuroscience， 2008， 2008： 852187-1-852187-3.

［6］MIN E X， GUO X F， LIU Q， et al. A Survey of Clustering with Deep Learning： From the Perspective of Network Architecture ［J］. IEEE Access， 2018， 6： 39501-39514.

［7］XIE J Y， GIRSHICK R B， FARHADI A. Unsupervised Deep Embedding for Clustering Analysis ［C］//International Conference on Machine Learning. ［S.l.］： PMLR， 2016： 478-487.

［8］GUO X F， GAO L， LIU X， et al. Improved Deep Embedded Clustering with Local Structure Preservation ［C］//International Joint Conference on Artificial Intelligence. New York： ACM， 2017： 1753-1759.

［9］VINCENT P， LAROCHELLE H， BENGIO Y， et al. Extracting and Composing Robust Features with Denoising Autoencoders ［C］//Machine Learning， International Conference. New York： ACM， 2008： 1096-1103.

［10］ZHANG J L， CHEN F， GUO Y N， et al. Multi-graph Convolutional Network for Short-Term Passenger Flow Forecasting in Urban Rail Transit ［J］. IET Intelligent Transport Systems， 2020， 14（10）： 1210-1217.

［11］GIRVAN M， NEWMAN M E J. Community Structure in Social and Biological Networks ［J］. Proceedings of the National Academy of Sciences， 2002， 99（12）： 7821-7826.

［12］KIPF T N， WELLING M. Semi-supervised Classification with Graph Convolutional Networks ［EB/OL］. （2016-09-09）［2022-02-15］. https：//arxiv.org/abs/1609.02907.

［13］BO D Y， WANG X， SHI C， et al. Structural Deep Clustering Network ［C］//Proceedings of the Web Conference. New York： ACM， 2020： 1400-1410.

［14］GUO X F， ZHU E， LIU X W， et al. Deep Embedded Clustering with Data Augmentation ［C］//Asian Conference on Machine Learning. ［S.l.］： PMLR， 2018： 550-565.

［15］TRIPATHY B K， ANVESHNTHAA S， GHELA S. t-Distributed Stochastic Neighbor Embedding （t-SNE） ［M］. ＼[S.l.]： Encyclopedia of Mathematical Geosciences， 2021： 1-9.

［16］RUDER S. An Overview of Gradient Descent Optimization Algorithms ［EB/OL］. （2016-09-15）［2022-02-18］. https：//arxiv.org/abs/1609.04747.

［17］GRIGORYAN A. Heat Kernel and Analysis on Manifolds ［M］. ［S.l.］： American Mathematical Society， 2009： 1-49.

［18］ABEYWICKRAMA T， CHEEMA M A， TANIAR D. K-Nearest Neighbors on Road Networks： A Journey in Experimentation and In-memory Implementation ［J］. Proceedings of the VLDB Endowment， 2016， 9（6）： 492-503.

［19］LEY M. DBLP-Some Lessons Learned ［J］. Proceedings of the VLDB Endowment， 2009， 2（2）： 1493-1500.

［20］STISEN A， BLUNCK H， BHATTACHARYA S， et al. Smart Devices Are Different： Assessing and Mitigating Mobile Sensing Heterogeneities for Activity Recognition ［C］//Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems. New York： ACM， 2015： 127-140.

［21］LECUN Y， BENGIO Y， HINTON G. Deep Learning ［J］. Nature， 2015， 521： 436-444.

［22］LEWIS D D， YANG Y， RUSSELL-ROSE T， et al. Rcv1： A New Benchmark Collection for Text Categorization Research ［J］. Journal of Machine Learning Research， 2004， 5： 361-397.

［23］KINGMA D P， WELLING M. Auto-Encoding Variational Bayes ［EB/OL］. （2013-12-20）［2022-01-30］. https：//arxiv.org/abs/1312.6114.

［24］KIPF T N， WELLING M. Variational Graph Auto-Encoders ［EB/OL］. （2016-11-21）［2022-02-01］. https：//arxiv.org/abs/1611.07308.

［25］PAN S R， HU R Q， LONG G D， et al. Adversarially Regularized Graph Autoencoder for Graph Embedding ［EB/OL］. （2019-01-08）［2022-02-10］. https：//arxiv.org/abs/1802.04407.

［26］YANG J W， PARIKH D， BATRA D. Joint Unsupervised Learning of Deep Representations and Image Clusters ［C］//IEEE Conference on Computer Vision and Pattern Recognition. Washington D.C.： IEEE Computer Society， 2016： 5147-5156.

［27］HUO G Y， ZHANG Y， GAO J B， et al. CaEGCN： Cross-Attention Fusion Based Enhanced Graph Convolutional Network for Clustering ［J］. IEEE Transactions on Knowledge and Data Engineering， 2021， 35（4）： 3471-3483.

（責(zé)任編輯： 韓 嘯）

收稿日期： 2022-05-20.

第一作者簡(jiǎn)介： 姚 博（1997—）， 女， 漢族， 碩士研究生， 從事深度圖聚類的研究， E-mail： byao_1@stu.xidian.edu.cn. 通信作者簡(jiǎn)介： 王衛(wèi)衛(wèi)（1990—）， 女， 漢族， 博士， 教授， 從事機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的研究， E-mail： wwwang@mail.xidian.edu.cn.

基金項(xiàng)目： 國(guó)家自然科學(xué)基金（批準(zhǔn)號(hào)： 61972264; 61472303; 61772389）.