基于矩阵循环叠加的网络特征结构表示

毕 阳，何嘉林,2，崔东旭，任卫平

(1.西华师范大学 计算机学院，四川 南充 637002；2.物联网感知与大数据分析南充市重点实验室，四川 南充 637002)

0 引言

在当今现实世界中有很多网络，例如银行客户网络，微博社交网络，生物蛋白质结构网络，都可以用节点和边组成的形式来研究.许多任务，例如多标签分类任务，多路链路预测任务，可以被很快速地表示并执行[1].但是随着形如微博社交网络，银行客户网络等网络的快速扩张，网络数据体量越来越大，如何处理并且高效处理大规模的网络成为了一个让人头疼的问题，如何将这些网络表示是解决这一难题的关键.在传统的方法当中，将网络用邻接矩阵进行表示，矩阵的每一行代表着网络中的每个点在网络中的特征向量，但是在大型网络中，这种表示方法所得矩阵向量维度极高，使得一些复杂的网络表示过程极其困难.针对此现象，近年来的网络表示学习被广泛应用于网络分析，通过顶点在网络中所扮演的角色为网络构建一个低维向量，极大地减少了时间成本和运算空间.本文提出一种方法，通过对矩阵的分解且不断更新得到最早的网络特征矩阵.与3种网络表示学习方法Line[2]，node2vec[3],Deepwalk[4]相比，我们的方法在多标签分类和多路链路预测上有着更好的表现.

1 基础概念

1.1 网络结构图

图 1 无权网络G

设G=(V,E)是一个无权网络，如图1所示.其中集合V是包含许多个顶点的顶点集，E则是边集合.在图1中集合V为(V1,V2,V3，…，V12),集合E为(E1,2，E1,3，E1,6，…，E12,7)传统方法将网络结构用高维的图邻接矩阵表示，这种表示方法虽然捕捉到了网络结构，但是由于其极大的矩阵维度，导致计算成本和所用空间过大，无法应用于大型网络.针对这个问题，网络表示学习的方法学习对应网络的函数f:V→Rd，将网络中的全部节点映射到低维向量空间Rd中，d表示维数.

1.2 多标签分类指标

设B(TPj,FPj,TNj,FNj)是一个特定的分类值，TPj，FPj，TNj，FNj分别表示准确率，精确率，召回率 和Fβ.这些值可以在以下两个模型中测试节点分类的性能[5].

(i) macro-F1model

(1)

(ii) micro-F1model

(2)

1.3 多路链路预测指标

AUC指标[6]用于测试链路预测方法的性能.AUC得到的值可以解释为随机选择的缺失链接比随机选择的不存在链接获得更高分数的概率.如果在n个独立的比较过程中，有n'次缺失的链接具有较高的分数，并且有n″次它们具有相同的分数，则AUC(用A表示)的值为：

(3)

2 算法及相关原理

2.1 奇异值分解

假设S是一个m×n阶矩阵，如此则存在一个分解使得S=UΣZ*.其中U是m×m矩阵；Σ是半正定m×n对角矩阵；而Z*即Z的共轭转置矩阵，是n×n矩阵.这样的分解就称作S的奇异值分解[7].Σ对角线上的元素Σi，Σi

即为S的奇异值.

(4)

2.2 矩阵循环叠加(Mscr)

在网络结构中，有些网络结构十分稀疏，从而会导致式(4)分解起来相对困难，会在式(4)的基础上进行改进，如式(5)所示.

(5)

(6)

为了防止过拟合，我们加入正则化项：

(7)

对于原始矩阵S，我们将上述过程称为一个完整的表示过程，当进行n个这样的过程时，将所得矩阵不断地通过更新，最终得到式(8)中的Sf.

(8)

3 实验

3.1 环境准备

本文实验硬件环境配置为i5-8400CPU和16GB内存.软件实验环境在Windows10中进行，软件环境配置为python3.7版本，pytorch1.8版本，实验所用数据如表1所示.

其中Blogcatalog[8]，Wikipedia[9]，DBLP，三个数据集被用作节点分类任务，Amazon，YouTube，Twitter数据集被用作多路链路预测任务.其中Blogcatalog，YouTube，Twitter数据集表示对应博客网络，YouTube视频网络，Twitter社交网络中用户之间的内在关系，Wikipedia数据集表示维基百科中词与词性之间的联系，DBLP则是一个论文网络.本实验运行时，规定了所有方法中，维度d都设置为128.对于deepwalk和Node2vec两种方法，设置步长为40，每个节点的步行次数为10.对于node2vec两个参数p和q都设置为0.25.

表1 数据集

3.2 实验结果

3.2.1 多标签分类

我们首先评估了Mcsr方法在节点分类任务上的性能表现.为了和其他几种方法比较，我们随机挑选一部分节点作为此次实验的训练集，余下的节点作为此次实验的测试集，所有方法的训练比率(TR)范围均从0.1～0.9.上述过程重复50次，所得Micro-F1分数取平均值即为所得方法分数.实验结果如图2所示.在Wikipedia和DBLP网络中，Mcsr方法优于其他三种方法.在DBLP网络中，Mcsr方法有着最好的表现，在Blogcatalog方法中，当TR>0.5时，Mcsr方法好于Deepwalk方法.在Blogcatalog网络和DBLP网络中，Deepwalk方法保持着良好的性能，均比其他2种方法稳定，但不及Mcsr方法.

图2 三种网络上的Micro-f1分数

3.2.2 多路链路预测

我们还评估了Mcsr在多路链路预测上的性能，本实验使用Amazon，YouTube，Twitter三种网络，并采用式(3)中的AUC指标来比较和其他三种方法的性能.网络中被移除的边的15%作为测试集，剩余边作为训练集，此次实验同样重复做50次，取结果平均值得到AUC分数.

结果如表2所示，从表2中可以看到，Mcsr在三个网络中均优于其他3种方法.

表2 三种网络上的AUC分数

在YouTube网络中，其他三种方法性能都比较接近.但Mcsr方法所得分数高于其他所有方法.在Amazon网络中，Mcsr相比表现最好的Line方法，性能提升了2.6%.在YouTube网络中，Mcsr相比表现最好的Deepwalk方法，性能提升了1.9%.在Twitter网络中，Mcsr相比表现最好的Node2vec方法提升了2.4%.与其他三种方法相比，我们的方法在多路链路预测任务上面能拥有更好的性能.

4 总结

本文实验结果表明，在对复杂网络结构用低维向量矩阵表示的过程中，我们的方法相比于传统的用邻接矩阵表示复杂网络结构的方法，节约了计算时间和空间.在多标签分类任务和多路链路预测任务实验结果中我们可以看出，我们的方法在性能上均优于其他三种方法.