基于異構融合和判別損失的圖嵌入聚類

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

關鍵詞： 圖聚類； 深度學習； 判別損失； 異構融合

中圖分類號： TP391 文獻標志碼： A 文章編號： 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

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

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

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

基于上述問題， 結合GCN和SDCN， 本文設計一個端到端訓練的深度圖嵌入聚類網絡， 從類內和類間兩個角度設計損失函數， 使同一類特征之間的距離小， 不同類特征之間的距離大. 此外， 本文在SDCN融合特征的基礎上引入一個圖解碼器， 對原始數據的內容信息以及結構信息進行重構， 通過最小化重構損失保證融合特征表示中包含高質量的結構信息， 從而更利于聚類. 在6個公開數據集上的實驗結果表明， 本文方法具有較高的泛化能力和聚類性能.

1 預備知識

1.1 圖卷積網絡

GCN是作用在圖數據上的圖表征提取方法， 網絡結構如圖1所示. GCN由兩層圖卷積層組成， 非線性激活函數為ReLU， 首先使用圖卷積網絡對圖中的節點進行卷積操作， 得到每個節點特征表示組成的特征矩陣：

3.3 方法性能對比

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

由表2和表3可見， 本文方法在大部分數據集上聚類性能優于其他方法. 對于圖數據集ACM，DBLP和Citeseer， 相比于SDCN， 本文方法的聚類性能指標ACC分別提升了2.30%，3.57%，5.52%； 對于非圖數據集HHAR，USPS和REUT， 本文方法的聚類性能指標ACC分別提升了2.04%，0.13%，0.55%. 可見， 本文方法更適用于圖數據集. 其原因可能有兩個： 1） 人為構造非圖數據集的拓撲結構導致結構信息不明確； 2） 非圖數據集的樣本數是圖數據集樣本數的3倍， 樣本數目太多導致網絡訓練困難. 實驗結果表明， 本文方法可有效增強特征表示的可判別性， 提升聚類性能.

3.4 消融實驗

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

由表4可見， 當從完整的方法中剔除任何一個損失函數時， 聚類性能都會下降， 證明了每個模塊對于聚類過程的促進作用. 剔除圖特征重構或圖結構重構時， 聚類性能下降程度相當， 說明特征與結構的重要性大致相同. 而當剔除卷積重構時， 聚類性能下降程度較大， 說明卷積自動編碼器提取的數據本身的信息非常重要， 證明了異質信息的交互可有效提升聚類性能.

3.5 收斂性分析

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

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

參考文獻

［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.

（責任編輯： 韓 嘯）

收稿日期： 2022-05-20.

第一作者簡介： 姚 博（1997—）， 女， 漢族， 碩士研究生， 從事深度圖聚類的研究， E-mail： byao_1@stu.xidian.edu.cn. 通信作者簡介： 王衛衛（1990—）， 女， 漢族， 博士， 教授， 從事機器學習和深度學習的研究， E-mail： wwwang@mail.xidian.edu.cn.

基金項目： 國家自然科學基金（批準號： 61972264; 61472303; 61772389）.