基于动态类簇形成博弈的属性图聚类方法

以微博、微信为代表的社交网络不仅包含丰富的节点属性信息,还蕴含复杂的网络拓扑信息,这些社交网络通常可被建模为属性图.传统的图聚类方法假设节点属性与网络拓扑共享同一类簇结构.然而,在真实社交网络中,节点属性与网络拓扑所对应的类簇结构并非完全一致.譬如,通过社团发现技术分析新浪微博的好友关注列表能够直观地获取聚集在同一群组的用户集合;而借助文本挖掘技术分析同一群组的用户生成内容却会发现用户讨论话题的分布广泛,体现出差异化的用户偏好特征.如何有效融合属性与拓扑信息对属性图进行聚类是理解、分析和可视化大规模社交网络的关键难题之一.为此,本文将属性图聚类建模为多目标优化问题,提出一种基于动态类簇形成博弈的属性图聚类方法.首先定义一种新颖的中心性指标度量节点的影响力,并提出一种启发式方法初始化属性图类簇质心;其次在动态博弈理论框架下,提出一种贪心的局部搜索策略更新节点类簇标签,并严格证明该局部搜索策略可使类簇结构收敛至局部帕累托最优解;最后设计一种基于多智能体自治计算的属性图聚类算法,该算法无需预设初始类簇个数,且复杂度近似线性于边的数目.为验证本文所提算法的性能,我们依次从三个方面来对其进行测试和评估.首先我们在Google+属性图上对所提算法进行了单独的收敛性分析.我们测试了算法中四个需要优化的目标函数(K-means损失函数、Havrda-Charvat生成熵、负模块度和负紧凑度)在三个不同的Bregman散度(欧氏距离平方、KL散度距离和余弦距离)设置下的收敛性情况.实验结果表明,四个目标函数能在50轮迭代之后达到收敛状态.然后,我们在4个大规模属性图上分别从聚类精度和可扩展性两个方面将本文所提算法与9个基准方法作了充分对比.对比结果表明,本文所提算法在NMI指标下比其它算法所得最优结果高出0.7%;而在AvgF1指标下比大多数算法所得的最优结果高出0.2%.在可扩展性方面,本文所提算法即使在最大规模的Google+属性图上也能在1个小时内计算出聚类结果.最后,我们在小规模PolBK数据集上进行了可视化分析.从可视化结果可以看出,在14轮迭代后本文所提算法就达到了稳定状态,与此同时找到了与真实情况接近的类簇结构.总体实验结果表明,本文方法能够准确发现大规模社交网络潜在的类簇结构,且同已有方法相比具备较好的有效性和高效性.

自监督对比的属性图联合表示聚类

现实世界中越来越多的复杂数据被表示为具有属性节点的图,因此属性图聚类是图挖掘中的一个重要问题。图神经网络在图结构数据的编码表示方面取得较好性能,但基于卷积操作或者注意力机制的图神经网络方法存在节点噪声、特征过度平滑、网络异质性、计算代价高昂等问题。基于深度学习方法如自编码器能够有效地提取节点属性表示,但不能包含丰富结构信息。因此提出了一种基于自监督训练和对比学习的图联合表示聚类方法(self-supervised contrastive graph joint representation clustering,SCRC)。使用自编码器预训练学习节点的属性表示,通过在图结构信息上增加对比损失信息,使用影响对比损失融合更加丰富的结构信息,联合图结构信息和属性表示,基于神经网络自监督训练机制迭代优化完成聚类任务。通过设计简单的线性模型,避免使用卷积和注意力机制,有效整合结构信息,使得运行速度更快。在广泛使用的引文网络数据上进行实验,对参数敏感性进行分析,验证了影响对比损失和自监督联合聚类的有效性。实验结果表明,所提出的方法取得了显著的性能提升,并且对节点噪声、特征过度平滑和网络异质性更具有鲁棒性。

困难样本采样联合对比增强的深度图聚类

针对困难样本挖掘的图聚类算法是最近的研究热点,目前算法存在的主要问题有:对比方法和样本对加权策略缺少良好的融合机制;采样正样本时忽略了视图内部的“假阴性”样本;忽视图级信息对聚类的帮助。针对上述问题,提出困难样本采样联合对比增强的图聚类算法。首先使用自编码器学习嵌入,根据计算的伪标签、相似度、置信度信息为表示学习设计一种自加权对比损失,统一不同视图下节点对比和困难样本对加权策略。通过调整不同置信区域样本对的权重,损失函数驱动模型关注不同类型的困难样本以学习有区分性的特征,提高簇内表示的一致性和簇间表示的差异性,增强对样本的判别能力。其次,图级表示经聚类网络投影,通过聚类对比损失最大化不同视图下聚类的表示一致性。最后联合两种对比损失,利用自监督训练机制进行迭代优化,完成聚类任务。该算法在5个真实数据集上与9个基准聚类算法对比,在4个权威指标上达到最优,聚类性能出色。消融实验表明两个对比模块的有效性和可迁移性。

多智能体系构架下的属性图分布式聚类算法

近年来属性图聚类受到了广泛关注,其目的是将属性图中的节点划分到若干簇中,使得每一个集群都有紧密的簇内结构和均匀的属性值。现有的理论主要是假设属性图中的节点或对象是为了协助优化某个给定的方程,而忽略了它们在现实生活中本身的属性。同时,一些开放性问题尚未得到有效解决,如异构信息集成、计算成本高等。为此,把属性图聚类问题理解为自身节点代理的集群形成博弈。为了有效地整合拓扑结构和属性信息,提出了基于紧密性和均匀性约束的节点代理策略选择。进一步证明了博弈过程将会收敛到弱帕累托纳什均衡。在实证方面,设计了一个分布式和异构的多智能体系统,给出了一个快速的分布式学习算法。该算法的主要特点是结果分区的重叠率可以由一个事先给定的阈值控制。最后,在现实社交网络上进行了模拟实验,并与目前先进方法进行比较,结果证实了所提算法的有效性。