本文介紹來自北航彭浩團隊的最新科研成果 ——DeSE 框架。通過軟分配結構熵量化圖結構，利用結構學習層（SLL）增強原圖、聚類分配層（ASS）學習節點嵌入與軟分配矩陣，結合雙損失優化，解決傳統方法依賴原始圖結構和聚類先驗的問題。在 Cora 等四個數據集上，DeSE 優于 DMoN 等八種基線，NMI、ACC 等指標領先，尤其在稀疏圖表現突出。消融實驗驗證核心模塊的有效性，超參分析顯示實驗設置與選擇，聚類數不確定時可自適應收斂，兼具可解釋性與魯棒性。

論文名稱： Unsupervised Graph Clustering with Deep Structural Entropy 論文鏈接： http://arxiv.org/abs/2505.14040 相關Talk： https://www.bilibili.com/video/BV1DB7BzQEZh

圖結構學習（GSL）在推薦系統、社區檢測等領域應用廣泛，其通過與下游任務結合優化圖拓撲并生成節點分類，實現魯棒語義嵌入和結構信息的學習。無監督圖聚類常采用對比損失學習圖結構嵌入，但早期方法如層次圖學習 [1]、基于結構的嵌入學習 [2] 等，嚴重依賴于原始圖結構，主要目標是通過最小化相鄰或結構相似的節點之間的距離來學習更好的節點嵌入，并且僅專注于在模型內對其進行優化（如圖1(a)所示）。這種對原始圖（通常是稀疏鄰接矩陣）的依賴嚴重限制了模型的性能。

為了解決這些問題，現有方法通過圖對比 [3]、圖自編碼器 [4] 等優化原始圖結構，但仍然依賴于學習到的嵌入來形成聚類（如圖1(b)所示），如最常用的K-Means算法需預先設定簇數。這樣“先嵌入后聚類” 模式的性能受制于表示學習質量與聚類算法配置，并且無法直接捕捉節點特征與自適應簇的本質關聯。此外，多數方法缺乏對圖結構的量化表示，可解釋性較差。

目前，無監督圖聚類面臨以下 3 個主要挑戰：

挑戰 1：如何克服原始圖結構稀疏性與強依賴性的限制？

現有方法過度依賴原始稀疏鄰接矩陣，忽略屬性相似節點間可能存在的非直接連接，導致模型無法有效捕捉潛在結構關聯，難以應對實際場景中節點連接稀疏或缺失的問題，限制了聚類性能的提升。

挑戰 2：如何解決嵌入學習與聚類過程的解耦問題？

傳統方法采用 “先嵌入后聚類” 模式，將表示學習與聚類分割為獨立步驟，且聚類結果受限于嵌入質量與聚類算法配置，無法在模型收斂過程中直接建立節點特征與自適應簇的內在聯系，導致聚類結果與結構語義的一致性不足。

挑戰 3：如何實現圖結構的量化表示并提升聚類可解釋性？

多數方法聚焦聚類結果而缺乏對圖結構的量化建模，難以揭示簇劃分的內在邏輯。現有結構優化指標（如模塊化）僅從邊期望差異角度刻畫簇結構，高度數節點主導連接，無法適應復雜場景中多中心節點跨類分布的結構特征，導致模型可解釋性較差。

為解決以上問題，作者提出 DeSE 框架，通過結構熵量化、結構學習層（SLL）、聚類分配層（ASS）及雙重優化機制，解決上述挑戰并提升聚類性能與可解釋性。DeSE從優化的結構種獲得最終的聚類（如圖1(c)所示），具體模型框架圖如圖2所示。

圖 1 三類模型的概念圖（（a）和（b）為現有模型，（c）為本文提出的 DeSE）圖 2 DeSE整體框架圖

DeSE 框架包含三個主要模塊：結構量化模塊、結構學習層（SLL）和聚類分配層（ASS）。具體而言：結構量化模塊引入軟分配結構熵，對圖結構信息進行量化，將離散聚類任務轉化為連續可微的優化目標。結構學習層在特征映射空間學習 K 近鄰屬性圖，以增強原始圖結構，解決節點間稀疏性和交互缺失問題。聚類分配層基于圖神經網絡（GNN），在增強圖中同時學習節點嵌入和軟分配矩陣，更新高層社區嵌入及簇增強圖結構。優化模塊整合各模塊，通過節點與簇間的結構熵損失和節點嵌入間的交叉熵損失優化學習過程。

二、方法2.1 結構量化

結構信息理論在學習圖節點的層次結構和簇劃分中具有顯著優勢，它通過量化圖結構的不確定性，將其轉化為數學可計算的形式。盡管已有研究將結構熵及其優化方法從簡單同構圖擴展至多關系圖和超圖，但結構熵的計算仍以離散方式進行。這一局限導致當前優化方法僅能執行合并操作（如節點對的貪心合并），無法滿足無監督圖聚類任務的需求 —— 期望結構熵不僅能將節點劃分為簇，還能提供可訓練的反饋以增強圖結構，傳統結構熵的局限性由此凸顯。

為解決這一問題，需要將節點與簇之間原始的二元 “屬于 / 不屬于” 關系（在分配矩陣中以離散值 0 或 1 表示）轉化為概率關系：節點不再唯一歸屬于單個簇，而是以不同概率屬于多個簇。這種方法更貼合現實場景，例如引用網絡中的跨學科論文 —— 盡管這類論文有主類別，但其研究內容也會涉及其他相關類別并產生關聯，這些信息對嵌入學習和結構優化具有重要價值。這種概率性的簇分配方式也被稱為 “軟分配”。

軟分配結構熵。結構信息理論基于節點通過邊的隨機游走量化圖結構的不確定性。當低層頂點根據第層的分配矩陣 屬于父頂點時，首先將公式 表示為各層節點熵的總和，并引入直接分配矩陣的概念：

其中，公式（1）中的 表示第層的結構熵，該層有 個節點，編碼樹的總高度為 。 表示第 層與第 層頂點之間的分配矩陣。如公式（2）所示， 是葉頂點（即圖中節點）與第 層頂點之間的直接分配矩陣，表示每個節點屬于第 層某個簇的概率。此外，作者重新定義切割邊和體積的計算與表示如下：

其中，第 層頂點 的體積 是所有節點度數的分配概率之和（公式（3））。 為所有節點的度向量，可通過邊權矩陣 計算得到， ， 是一個長度為 的向量，所有元素均為 1，權矩陣的計算詳見 2.2 節）。 的下標表示矩陣的第列向量，表示圖中 個節點直接聚類到第 層第 個簇的概率，而第 個頂點在 層代表第 個簇。 表示第 個頂點在 層的切割值，其計算方法是頂點 的體積 與其內部體積 之差。內部體積 表示為所有邊的加權概率之和，其中概率指的是一條邊連接的兩個節點在 層屬于同一個簇 的可能性。因此，結構熵的計算修改為：

其中，軟分配方法將單一父頂點的原始體積替換為所有父頂點體積的概率和 。 為第 層所有 個頂點體積的向量表示，根據公式（3）可進一步簡化為 。

2.2 結構學習層

在圖聚類任務中，輸入通常為節點特征和鄰接矩陣 。傳統方法基于原始結構訓練節點特征以生成嵌入，但 中的連接未必完全符合聚類目標。例如，引用網絡中相似主題的論文可能無直接關聯（如聚焦不同應用領域的神經網絡論文），或存在關聯的論文可能分屬不同主題（如跨學科論文）；產品共購網絡中，共同購買的商品可能為互補品（如電腦與顯示器）而非同類品。原始圖結構 的這種不匹配會導致聚合過程中的信息丟失，影響圖聚類效果。

SLL 旨在利用可用特征信息增強原始圖結構，并在訓練過程中動態優化和更新圖來增強原始圖結構。由于原始特征常為高維稀疏二進制向量，首先通過多層感知機（MLP）將節點特征映射到低維稠密空間（如圖 2 II 所示）。基于這些嵌入，采用 K 近鄰算法（KNN）為每個節點選擇前 個鄰居并創建權重為 1 的邊，構建屬性圖，數學表示為：

其中，MLP 輸入維度為 ，隱藏層與輸出層維度均為， 為 MLP 參數。KNN 為 近鄰操作，所得鄰接矩陣 的每行表示對應節點的鄰居選擇。由于 KNN 通過節點間距離排序選擇鄰居，可能存在單向鄰居（即節點 是 的前 個鄰居，但 未必是 的前 個鄰居）。考慮到單向與雙向鄰居選擇的差異，作者將屬性圖的鄰接矩陣調整為：

這確保屬性圖的鄰接矩陣對稱，同時仍然部分保留單向和雙向鄰居選擇信息。最后，將原始圖鄰接矩陣與屬性圖鄰接矩陣融合，得到增強圖：

其中， 為超參數，控制屬性圖在融合中的權重； 為新的邊權鄰接矩陣，用于 2.1 節的軟分配結構熵及后續計算。

2.3 聚類分配層

聚類分配層利用初始嵌入和鄰接矩陣學習節點的軟分配和嵌入，同時在聚合后更新圖結構和簇嵌入。該層包含三個組件：嵌入學習器 、軟分配學習器 和聚合器 ，如圖 2 III 所示。

嵌入學習器。嵌入學習器基于 GNN 架構，數學表達式為：

其中， 對初始嵌入 進行線性變換，映射到嵌入空間，隨后聚合相連節點的平均嵌入以生成新的節點嵌入，并應用激活函數。線性變換的可學習參數表示為 。

軟分配學習器。軟分配學習器通過注意力機制擴展 GNN 架構，數學表達式為：

其中， 對初始嵌入 進行線性變換至簇空間（維度等于簇數），計算每條邊的注意力矩陣 作為聚合權重，通過非平均嵌入聚合得到簇嵌入。線性變換的可學習參數為 。注意力計算過程中，將邊兩端節點的拼接嵌入線性變換至一維空間（權重空間），經激活和歸一化后得到權重。 和 分別表示節點 和 的嵌入，注意力機制中線性變換的可學習參數表示為 。

聚合器。聚合器的目標是更新簇的嵌入和鄰接矩陣。作者通過節點嵌入的概率和計算簇嵌入，記為 。新鄰接矩陣由屬性圖鄰接矩陣與結構圖鄰接矩陣融合而成，類似 2.2 節公式 (8) 的結構學習方法，具體計算如下：

其中， 表示 在聚類中的可學習參數，新的加權鄰接矩陣為 。

2.4 優化

首先按 2.2 節所述增強原始圖，在新的加權鄰接矩陣 上進行一輪 GNN 傳播，將稀疏高維特征向量 轉換為初始節點嵌入 。隨后通過多個 ASS 模塊（2.3 節）學習不同層的軟分配矩陣 。作者采用軟分配結構熵損失（SE 損失）和負采樣交叉熵損失（CE 損失）優化圖聚類任務。設正負邊集合為 ，且正負邊數量相等。CE 損失計算如下：

其中， 表示節點 與 之間存在邊的概率，基于兩者嵌入的距離計算； 為真實標簽（指示邊是否存在）。最終損失由 2.1 節計算的 SE 損失和 CE 損失組成：

其中， 和 分別為 SE 損失和 CE 損失的系數超參數。

2.5 復雜度分析

對 DeSE 各組件的時間復雜度進行分析：

結構學習層（SLL）：時間復雜度主要由 MLP 和 KNN 貢獻，分別為 和 （ 為節點數， 為原始特征維度， 為嵌入維度）。聚類分配層（ASS）：嵌入學習器和軟分配學習器的復雜度分別為 和 。損失計算：結構熵損失（SE loss）的復雜度為 （c為簇數），交叉熵損失（CE loss）為 （M為邊數）。由于簇數 通常較小，模型總時間復雜度可歸納為： ,進一步簡化為 ，表明模型在大規模圖數據上具有較好的計算效率。

三、實驗

為驗證 DeSE 框架的有效性，作者在 Cora、Citeseer、Computer 和 Photo 四個基準數據集上（詳見表1），與 DMoN、MinCut 等 8 個基線模型進行對比實驗，采用 NMI、ARI、ACC、F1 等指標評估聚類性能，并通過消融實驗、敏感性分析和魯棒性測試深入分析模型特性（相關結果詳見表2、圖3）。

表 1 數據集統計信息

DeSE 在聚類性能上顯著優于基線模型：在 16 項評估指標中 12 項表現最優，NMI 指標在所有數據集上均達最佳（詳見表 1）。其通過結構量化與增強圖學習，實現了大小簇的精準劃分，如圖 3 所示，相比 RDGAE 對小簇的誤判、EGAE 和 MinCut 對大簇的分散預測，DeSE 的聚類結果更聚焦準確。

表 2 四種數據集上不同方法在 NMI、ARI、ACC 和 F1 指標上的對比（最佳結果用粗體表示，次佳結果帶下劃線）

圖 3 DeSE、EGAE、MinCut 和 RDGAE 在 Photo 數據集上的聚類結果（縱軸表示真實簇包含的節點數，橫軸表示模型預測的簇節點數。熱圖中每個圓圈表示真實簇中被預測屬于簇的節點數，圓圈大小代表節點數量，顏色深淺表示這些節點在真實簇中的占比，顏色越深比例越高）

消融實驗表明，結構學習層（SLL）對稀疏圖結構優化至關重要（如 Cora 數據集去除 SLL 后 ACC 和 F1 未定義），結構熵損失（SE loss）則通過量化結構信息穩定簇結構（密集圖去除 SE loss 后指標嚴重下降，詳見表 3）。

表 3 四個數據集上不含 SLL 模塊和 SE 損失的對應測試結果。

敏感性分析顯示，超參數 時模型性能最佳（引入過多鄰居易引入噪聲，隨機邊設置導致性能顯著下降，詳見圖 4、表 4）；屬性圖權重 需適配數據集（過大權重會干擾原始圖結構，詳見圖 5）；SE loss 系數雖小但對性能提升關鍵（詳見表 5）。

圖 4 超參數對NMI和ACC指標的敏感性。表 4 DeSE 在基于不同度數分布的值下的性能表現。

圖 5 四個數據集上超參數 對四項指標的敏感性。
表 5 超參數 和 對NMI指標的敏感性分析。

對類簇數的魯棒性實驗表明，當預設簇數偏離真實值時，DeSE 仍能收斂至正確簇數并保持高 NMI/ARI，而基線模型因依賴預設簇數導致性能驟降（詳見圖 6、表 6）。案例學習中的迭代實驗進一步驗證，模型可通過自適應調整簇數逐步逼近真實分布（以 Cora 為例，經多輪迭代從 2708 簇收斂至 7 簇，詳見表 7）。

表 6 基線模型對簇數的魯棒性表現。

圖 6 Cora 數據集上簇數的魯棒性表現。
表 7 簇數未知時Cora數據集的案例研究。 四、結論

本文中作者提出了一種融合深度結構熵的新型無監督圖聚類框架 DeSE，旨在解決結構量化和結構學習的挑戰以提升聚類性能。作者引入了一種利用軟分配計算結構熵的方法，并設計了一個結構學習層，用于基于節點特征優化原始圖。此外，聚類分配層聯合學習節點嵌入和軟分配矩陣，通過一種新的優化方法生成節點聚類，該方法同時最小化 SE 損失和 CE 損失。在四個數據集上的實驗表明，DeSE 在 NMI、ARI、ACC 和 F1 等指標上優于 8 個基線模型，并可視化了聚類效果和誤差。消融實驗證明了 SLL 模塊和結構熵損失的關鍵作用；超參敏感性分析實驗顯示模型對近鄰數、鄰接矩陣融合權重、損失權重等參數設置的依據。此外，DeSE 對類簇數的魯棒性分析和在簇數未知場景下的案例研究進一步凸顯了其穩健性。該研究凸顯了結構信息論在圖結構學習中的潛力，并可能為研究可訓練的軟分配結構熵在特征和結構融合方面的應用開辟新的途徑，有望推動無監督圖聚類在推薦系統、社交網絡分析等領域的應用發展。

篇幅原因，我們在本文中忽略了諸多細節，更多細節可以在論文中找到。感謝閱讀！

參考文獻

[1]Ya-Wei Eileen Lin, Ronald R Coifman, Gal Mishne and Ronen Talmon. Hyperbolic diffusion embedding and distance for hierarchical representation learning. In International Conference on Machine Learning, 2023.

[2]Tianshu Lyu, Yuan Zhang and Yan Zhang. Enhancing the network embedding quality with structural similarity. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017.

[3]Kaize Ding, Yancheng Wang, Yingzhen Yang and Huan Liu. Eliciting structural and semantic global knowledge in unsupervised graph contrastive learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.

[4]Nairouz Mrabah, Mohamed Bouguessa, Mohamed Fawzi Touati and Riadh Ksantini. Rethinking graph auto-encoder models for attributed graph clustering. IEEE Transactions on Knowledge and Data Engineering, 2022.

llustration From IconScout By IconScout Store

-The End-

本周上新！

掃碼觀看！

“AI技術流”原創投稿計劃

TechBeat是由將門創投建立的AI學習社區（www.techbeat.net）。社區上線600+期talk視頻，3000+篇技術干貨文章，方向覆蓋CV/NLP/ML/Robotis等；每月定期舉辦頂會及其他線上交流活動，不定期舉辦技術人線下聚會交流活動。我們正在努力成為AI人才喜愛的高質量、知識型交流平臺，希望為AI人才打造更專業的服務和體驗，加速并陪伴其成長。

投稿內容

// 最新技術解讀/系統性知識分享 //

// 前沿資訊解說/心得經歷講述 //

投稿須知

稿件需要為原創文章，并標明作者信息。

我們會選擇部分在深度技術解析及科研心得方向，對用戶啟發更大的文章，做原創性內容獎勵

投稿方式

發送郵件到

melodybai@thejiangmen.com

或添加工作人員微信（yellowsubbj）投稿，溝通投稿詳情；還可以關注“將門創投”公眾號，后臺回復“投稿”二字，獲得投稿說明。

關于我“門”

將門是一家以專注于數智核心科技領域的新型創投機構，也是北京市標桿型孵化器。 公司致力于通過連接技術與商業，發掘和培育具有全球影響力的科技創新企業，推動企業創新發展與產業升級。

將門成立于2015年底，創始團隊由微軟創投在中國的創始團隊原班人馬構建而成，曾為微軟優選和深度孵化了126家創新的技術型創業公司。

如果您是技術領域的初創企業，不僅想獲得投資，還希望獲得一系列持續性、有價值的投后服務，歡迎發送或者推薦項目給我“門”:

bp@thejiangmen.com

點擊右上角，把文章分享到朋友圈