KDD 2025 | 北航提出DeSE框架，融合深度结构熵以提升图聚类性能|北航|向量|深度思考模型|算法|聚类|鲁棒性

本文介绍来自北航彭浩团队的最新科研成果 ——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所示。

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）。

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）。

对类簇数的鲁棒性实验表明，当预设簇数偏离真实值时，DeSE 仍能收敛至正确簇数并保持高 NMI/ARI，而基线模型因依赖预设簇数导致性能骤降（详见图 6、表 6）。案例学习中的迭代实验进一步验证，模型可通过自适应调整簇数逐步逼近真实分布（以 Cora 为例，经多轮迭代从 2708 簇收敛至 7 簇，详见表 7）。

本文中作者提出了一种融合深度结构熵的新型无监督图聚类框架 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）投稿，沟通投稿详情；还可以关注“将门创投”公众号，后台回复“投稿”二字，获得投稿说明。

关于我“门”

将门是一家以专注于数智核心科技领域的新型创投机构，也是北京市标杆型孵化器。公司致力于通过连接技术与商业，发掘和培育具有全球影响力的科技创新企业，推动企业创新发展与产业升级。