引用本文

张建朋, 裴雨龙, 刘聪, 李邵梅, 陈鸿昶. 基于因子图模型的动态图半监督聚类算法. 自动化学报, 2020, 46(4): 670-680. doi: 10.16383/j.aas.c170363

ZHANG Jian-Peng, PEI Yu-Long, LIU Cong, LI Shao-Mei, CHEN Hong-Chang. A Semi-supervised Clustering Algorithm Based on Factor Graph Model for Dynamic Graphs. ACTA AUTOMATICA SINICA, 2020, 46(4): 670-680. doi: 10.16383/j.aas.c170363

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170363

关键词

半监督聚类，进化因子图模型，特征提取，动态图 

摘要

针对动态图的聚类主要存在着两点不足:首先, 现有的经典聚类算法大多从静态图分析的角度出发, 无法对真实网络图持续演化的特性进行有效建模, 亟待对动态图的聚类算法展开研究, 通过对不同时刻图快照的聚类结构进行分析进而掌握图的动态演化情况.其次, 真实网络中可以预先获取图中部分节点的聚类标签, 如何将这些先验信息融入到动态图的聚类结构划分中, 从而向图中的未标记节点分配聚类标签也是本文需要解决的问题.为此, 本文提出进化因子图模型(Evolution factor graph model, EFGM)用于解决动态图节点的半监督聚类问题, 所提EFGM不仅可以捕获动态图的节点属性和边邻接属性, 还可以捕获节点的时间快照信息.本文对真实数据集进行实验验证, 实验结果表明EFGM算法将动态图与先验信息融合到一个统一的进化因子图框架中, 既使得聚类结果满足先验知识, 又契合动态图的整体演化规律, 有效验证了本文方法的有效性.

文章导读

如今越来越多的数据可以抽象为具有关联关系的图数据(也称网络数据), 典型例子包括网页链接形成的Web网络图, 用户关联交互的社交网络, 蛋白质相互作用网络.通常, 网络中的节点可以与相应的聚类标签相关联, 并且这些标签可以具有许多形式, 例如人口统计标签、兴趣、群组等.如何向图中的未标记节点分配标签是经典的半监督聚类问题.然而, 随着网络规模的增加和图节点之间复杂的关系使网络图的节点标签标注成本昂贵以及难以获得的特点.因此, 如何给网络中未标注的节点进行半监督聚类的问题最近引起了广泛的关注.

当前动态图聚类问题主要面临以下挑战: 1)当前研究大多数集中于静态网络[1-3].事实上, 许多真实网络图结构是随时间变化而不断演变的, 即图中的节点和边随时间的变化而更新.例如, 社交网络中的用户动态添加、删除朋友.在这种动态场景中, 时间属性信息对未标注节点的半监督聚类问题有很重要的作用.然而现有的经典算法诸如Girvan-Newman (GN[2])、Fast Newman (FN[3])、标签传播[4]等诸多方法大多从静态图分析的角度出发, 无法针对真实网络持续演化的特性进行有效的建模[5]. 2)真实网络中我们是可以预先获取图中部分节点对应的聚类标签(例如政治、兴趣, 加入群组标签), 如何将已有的先验信息融入到动态图的聚类划分中, 并对动态图进行半监督聚类的相关研究尚未成熟[6]. 3)如何对图节点进行有效的特征提取仍未得到很好的解决.文献[7]选择5种类型的特征, 即同源、三角闭合、范围、嵌入和结构洞, 用于节点的分类问题.文献[8]计算几个预定义的网络属性作为特征表征, 包括归一化节点度、聚类系数、共同邻居等.然而, 这些特征提取方法存在复杂度较高, 效果差的缺点.因此, 难以在不同的聚类任务中推广使用.

为了解决这些问题, 本文提出进化因子图模型(Evolution factor graph model, EFGM)用于动态图节点的半监督聚类问题, 将动态图与先验信息融合到统一的进化因子图框架中, 这样既使得聚类结果满足先验知识, 又可以契合动态图的整体演化规律.具体而言, 动态图以一系列图快照的形式组织, 本文在进化因子图模型中基于节点特征, 节点相关性和时间相关性分别设计三种类型的因子:包括节点因子、边邻接因子和进化因子来对图的相应快照进行建模.其中节点因子和边邻接因子可以捕获图结构的全局和局部性质, 而进化因子可以有效地利用时间快照信息.为了解决图中特征提取的问题, 本文在动态图中引入Node2vec[9]图嵌入的特征提取方法, 此特征提取过程中并不需要复杂的特征工程与外部知识就可以实现图的特征提取.

本文工作的主要贡献可归纳如下:

1) 提出进化因子图模型(EFGM)用于动态图节点的半监督聚类问题, 本模型通过捕获动态图的节点属性、边邻接属性和时间属性作为相应的因子应用到进化因子图模型中, 有效解决了动态图的半监督聚类问题.

2) 采用真实数据集评估EFGM的聚类效果, 所提模型在不同的评价指标均取得了不错的聚类效果.此外, 本文对特征维度、训练数据大小和图特征提取方法进行了敏感性分析, 进一步验证了算法的鲁棒性.

本文的后续部分安排如下:第1节对相关工作进行简要回顾; 第2节对问题进行形式化定义; 第3节对所提的进化因子图模型进行了详细阐述; 第4节对所提方法的有效性进行了实验验证; 第5节对本文所做的工作进行了总结和展望.

图 1  进化因子图模型示意图

图 2  特征数目对NMI指标的影响

图 3  特征数目对概率误差的影响

本文提出了一个进化因子图模型(EFGM), 通过在动态图中融合已有的先验信息对动态图中的节点进行半监督聚类分析.该模型通过捕获动态图的节点属性、边邻接属性和时间属性作为相应的因子应用到进化因子图模型中.此外, 为了突破图特征提取的限制, 本文引入了Node2vec图嵌入方法从图中提取特征.在真实网络数据集上进行实验, 所提模型可以有效地提高动态图聚类的精度.同时本文对特征维度、训练数据大小和图特征提取方法所产生的影响进行了分析, 进一步验证了算法的鲁棒性.

未来, 本文将研究如何更好的图提取特征方法.由于用户生成内容(UGC)易于访问, 因此动态场景中如何整合UGC信息对节点的标注非常重要.此外, 随着网络规模的急剧增加, 研究针对大规模网络的高效聚类算法具有重要意义.

作者简介

张建朋

荷兰埃因霍温理工大学博士研究生, 中国国家数字交换系统工程技术研究中心助理研究员.主要研究方向为数据流挖掘. E-mail:zhangjianpeng0309@gmail.com

刘聪  

荷兰埃因霍温理工大学博士生.主要研究方向为流程挖掘, 软件工程. E-mail: liucongchina@163.com

李邵梅  

中国国家数字交换系统工程技术研究中心副研究员.主要研究方向为图像处理与模式识别. E-mail: lishaomei@ndsc.com.cn

陈鸿昶  

中国国家数字交换系统工程技术研究中心教授.主要研究方向为电信网信息关防. E-mail: chenhongchang@ndsc.com.cn

裴玉龙  

荷兰埃因霍温理工大学博士生.主要研究方向为数据挖掘, 机器学习.本文通信作者. E-mail: feilong0309@sina.com