欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

SCI期刊论文
当前位置:首页 > SCI期刊论文
基于随机化矩阵分解的网络嵌入方法
来源:一起赢论文网     日期:2021-11-25     浏览数:411     【 字体:

 第44 第3 2021 年3 月计 算机 学 报CHINESEJOURNALOFCOMPUTERSVol .44No. 3Mar. 2021基于随机化矩阵分解的网络嵌入方法谢雨洋 冯 栩 喻文健 唐 杰(清华大学计算机科学与技术系 北京 10008 4)(北京信息科学与技术国家研究中心 北京 100 08 4)摘 要 随着互联网的普及, 越来越多的问题以社交网络这样的网络形式出现. 网络通常用图数据表示, 由于图数据处理的挑战性, 如何从图中学习到重要的信息是当前被广泛关注的问题. 网络嵌人就是通过分析图数据得到反映网络结构的特征向量, 利用它们进而实现各种数据挖掘任务, 例如边预测、节点分类、网络重构、标签推荐和异常检测. 最近, 基于矩阵分解的网络嵌人方法NetMF被提出, 它在理论上统一了多种网络嵌人方法, 并且在处理实际数据时表现出很好的效果.然而, 在处理大规模网络时, NetMF需要极大的时间和空间开销. 本文使用快速随机化特征值分解和单遍历奇异值分解技术对NetMF进行改进, 提出一种高效率、且内存用量小的矩阵分解网络嵌人算法eNetMF. 首先, 我们提出了适合于对称稀疏矩阵的随机化特征值分解算法freigs, 它在处理实际的归一化网络矩阵时比传统的截断特征值分解算法快近10 倍, 且几乎不损失准确度. 其次, 我们提出使用单遍历奇异值分解处理NetMF方法中高次近似矩阵从而避免稠密矩阵存储的技术, 它大大减少了网络嵌人所需的内存用量.最后, 我们提出一种简洁的、 且保证分解结果对称的随机化单遍历奇异值分解算法, 将它与上述技术结合得到eNetMF算法. 基于5 个实际的网络数据集, 我们评估了eNetMF学习到的网络低维表示在多标签节点分类和边预测上的有效性.实验结果表明, 使用eNetMF替代NetMF后在后续得到的多标签分类性能指标上几乎没有损失, 但在处理大规模数据时有超过40倍的加速与内存用量节省. 在一台32 核的机器上, eNetMF 仅需约1.3h即可对含一百多万节点的YouTube 数据学习到网络嵌人, 内存用量仅为120GB, 并得到较高质量的分类结果. 此外, 最近被提出的网络嵌人算法NetSMF 由于图稀疏化过程的内存需求太大, 无法在256GB内存的机器上处理两个较大的网络数据, 而ProNE算法则在多标签分类的结果上表现不稳定, 得到的Macro FI 值都比较差.因此,eNetMF算法在结果质量上明显优于NetSMF和ProNE算法. 在边预测任务上,eNetMF算法也表现出与其它方法差不多甚至更好的性能.关键词 网络嵌人; 网络表示学习; 随机化特征值分解; 单遍历奇异值分解; 多标签节点分类中图法分类号TP18DOI号10.11897/SP.J.1016 .2021. 00447LearningNetworkEmbeddingwithRandomizedMatrixFactorizationXIEYu YangFENGXuYUWenJi anTANGJi e{ DeparLmenLofComputerSci enceandTechnology? TsinghuaUniversi ty? Beiji ng1000 84)(BeijingNationalResearchCent erforInformationSci enceandTechnology? Tsi nghuaUni versity?Beiji ng1000 84)AbstractWiththepopularityoftheInternet ,moreandmoreprobl emsappearintheformofnetworkssuchassocialnetworks. Networksareoftenorganizedbygraphdataanditiswi del yacceptedthatgraphdataissophisticatedandchal l engi ngtodealwith.Therefore,howtol earni mportanti nformati onfromthegraphiscurrentl yawidespreadconcern.Networkembeddi ng,whichai mstol earnl atentrepresentati onsfornetworks,isanimportantfiel di ndatamini ng. Theresul tofnetworkembeddi ngshoul dpreservenetworkstructureandcanbeusedasthefeaturesforfurtherappl i cationsondatamini ngtasksl i kel i nkpredi cti on,nodecl assifi cati on,networkreconstructi on,tagrecommendati onandanomal ydetecti on.Skip grambasedalgorithmsli ke收稿日期:20 20 03 20; 在线发布日期:2020 08 23 . 本课题得到科技创新2030“新一代人工智能”重大项目(2020AAA0103502) 及国家自然科学基金( 618 7220 6) 资助. 谢雨洋, 博士研究生, 主要研究方向为数据挖掘、 矩阵算法. Email: xyyl8@mailS.tsinghua.edu.cn.冯 栩, 博士研究生, 主要研究方向为矩阵算法. 喻文健( 通信作者) , 博士, 副教授, 中国计算机学会( CCF) 会员, 主要研究方向为集成电路计算机辅助设计、 矩阵算法. Email :yuwj @tsi nghua.edu.cn. 唐 杰, 博士, 教授, 中国计算机学会(CCF) 会员, 主要研究领域为社交网络挖掘与学术知识图谱.448 计 算机 学 报 2021年DeepWal k,LINE,node2vechavebeencommonl yconsi deredaspowerfulbenchmarksol uti onsforeval uati ngnetworkembeddi ngresearch.Recentl y,networkembeddingasmatri xfactorizati on(NetMF)wasproposed. ItshowsthatDeepWal ki sactual lyi mpl i ci tl yfactori zi nganetwork’snormal izedLaplaci anmatrix,andLINE,i ntheory,isaspecialcaseofDeepWal k.NetMFtheoreti cal l yunifi esseveralnetworkembeddi ngmethodsandshowsi tssuperi ori tywhenprocessi ngtherealnetworkdata.However,theexcessi veruntimeandstorageofNetMFl imi tsi tsusageonl arge scal edata.Inthi swork,weusefastrandomi zedeigenval uedecomposition( EVD)andsi ngl epasssi ngul arval uedecomposi ti on(SVD)toi mproveNetMFandpresentaneffici entrandomi zedmatri xfactori zationbasednetworkembeddi ngalgori thm( eNetMF).Firstly,weproposeafastrandomizedEVDalgorithm( freigs)forsparsematri x.Itisabout10Xfasterthantradi ti onaltruncatedEVDalgorithmsforthenormal i zednetworkmatri x,whi lekeepi ngaccuracy. Secondly,weproposetousesingl e passSVDapproachtoprocesshigh orderproxi mi tymatri xintheNetMF,sothatwecanavoidstoringthelargedensematri xandlargelyreducethememorycostfornetworkembedding. Thirdl y,weproposeasi mplified,randomi zedsi ngl epassSVDalgorithmthatguaranteesasymmetricdecompositionresult. Combi ni ngtheabovetechniques,wefinal lyobtaintheeNetMFalgorithm.Withfi verealnetworkdatasets, weeval uatetheefficiencyandeffecti venessoftheeNetMFalgorithmonmul til abelnodeclassi ficati onandli nkpredicti on,commonl yusedtasksfornetworkembeddi ngeval uati on.Experi mentalresul tsshowthati ntermsofthemetricsMacr〇 FlandMicroFl,theembeddi nggeneratedbyeNetMFhasthesameperformanceasNetMFi nmul til abelnodecl assi ficati on. Foral arge scal egraphdata,eNetMFexhi bitsmorethan40Xaccel erati onandmemoryusagesavingoverNetMF.Onamachinewith32cores,eNetMFtakesonl y1.3 hand120 GBmemorytol earnagoodnetworkembeddi ngforthel argesttestdata(YouTube)whichhasmorethanonemil li onnodes.Inadditi on,duetothememorycostofspectralsparsi fication,therecentl yproposednetworkembeddi ngalgorithmNetSMFcannothandl etwol argenetworkdataonamachi newi th256GBmemory,whi l etheProNEalgori thmproducesunstabl eresul tsofmulti l abelnodecl assifi cati on. Tobepreci se,Macr〇Flobtai nedwi thProNEi sgeneral l ypoor. Therefore,theeNetMFalgori thmi sadvantageoustotheNetSMFandProNEalgorithmsintermsofperformance. Inthel i nkpredicti ontask,theeNetMFalgori thmachi evesbetterorcomparabl eperformancewhencomparedtootherbasel i nes.Keywordsnetworkembeddi ng;networkrepresentati onl earni ng;randomi zedeigenval uedecomposi ti on;si ngl epasssi ngul arval uedecomposi ti on;mul ti l abelnodecl assifi cati oni 引 言社交网络等大规模复杂网络的挖掘与智能分析是当前的研究热点. 这种网络包括微信、微博用户之间通过好友关系和互相联动形成的在线社交网络、学术论文之间的引用关系形成的网络[ 1 ]等等. 进行图数据挖掘主要有图卷积网络和网络嵌人两种方法. 网络嵌人一般不考虑节点的属性, 侧重于学习节点的拓扑结构, 而图卷积网络可以将节点的属性作为特征一起学习, 对于属性敏感的实验数据, 图卷积网络的效果要更好, 但由于很多网络数据缺少节点属性特征, 图卷积网络对此类数据节点拓扑结构的学习不如网络嵌人, 因此网络嵌人在图数据挖掘中占有很重要的地位. 应用网络嵌人的方法对网络进行分析, 首先要将网络用图的邻接矩阵表示. 接下来, 还要将网络中的每个节点映射到一个低维稠密实数向量上, 这样可以很好地保存节点的拓扑结构信息, 同时有利于使用机器学习等智能处理方法进行后续分析. 因此网络嵌人的目标就是将网络映射到潜在的低维空间, 得到网络节点的低维表示[ 2 ]. 研究表明, 网络嵌人技术可以促进各种网络分析与应用[3], 例如边预测、节点分类、 网络重构、标签推荐和异常检测. 通常, 基于传统拓扑的网络表示直接使用谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 4493 期对应图的邻接矩阵, 但这可能包含噪声或冗余信息.若使用网络嵌人技术, 每个节点都由包含潜在信息的向量表示, 因此许多网络分析中的迭代或组合的问题可以通过计算映射函数, 距离度量或嵌人向量运算的方式解决, 从而避免了高复杂度.主要的网络嵌人方法包括DeepWalk?、LINE[4]、node2vec[5]、metapath2vec[6]等, 它们都是基于skipgram的模型 ? 最近, 文献 [7]指出DeepWal k和LINE都可以看成是基于矩阵分解的技术, 并提出了一种基于矩阵分解的网络嵌人方法NetMF, 基于它在后续进行网络节点多标签分类时表现出比使用DeepWal k和LINE更好的性能. 然而, NetMF在处理超大规模网络时需要巨大的内存开销和计算成本, 这主要是由于它得到的高次近似矩阵是稠密的. 后续, 人们基于谱图稀疏化理论对NetMF进行了改进, 得到了利用谱图稀疏化理论和稀疏矩阵分解的网络嵌人方法NetSMF[8]和Pr〇NE[9], 这使得处理超大规模网络成为可能. 但是, 稀疏化矩阵的过程仍然需要大量的内存, 这使得NetSMF的应用受到一定的限制, 而ProNE得到的网络嵌人在应用时的效果也存在不稳定的问题.另一方面, 牺牲少量准确度的随机化低秩矩阵分解方法由于其适用于现代计算机体系结构和某些大数据应用场景正得到越来越多的关注[1"1 1]. 本文将随机化矩阵分解技术与网络嵌人方法NetMF相结合, 提出了一种快速、 节省内存、 且保证准确度的网络嵌人算法eNetMF. 具体的创新点如下:(1) 提出使用单遍历奇异值分解处理NetMF方法中高次近似矩阵从而避免存储此稠密矩阵的思路, 显著减少了NetMF方法所需的内存开销.(2) 提出针对稀疏对称矩阵的随机化特征值分解算法, 并调节需进行特征值分解的归一化网络矩阵奇异值衰减速度, 从而在保证准确性的同时显著加快了NetMF方法中高次近似矩阵的构造.(3) 提出一种简洁的且保证分解结果对称的随机化单遍历奇异值分解算法, 将它用于NetMF算法中减少了计算时间、 又保证了网络嵌人的质量.实验结果表明, 在相对较大的真实数据集上, 随机化特征值分解算法比传统截断特征值分解算法快10 倍, 且几乎没有误差. 而进行网络嵌人后再做节点多标签分类和边预测的实验中, eNetMF算法在保持NetMF结果质量的同时大大减少了其计算时间与内存用量. 例如, 对Flickr 数据eNetMF的运行时间和内存用量分别为NetMF的1/41 和1/46, 而对于节点数超过1 百万、NetMF与NetSMF由于内存需求太大无法处理的YouTube 数据, eNetMF只需1.3 h和120GB 内存开销即可得到网络嵌人, 并取得很好的多标签分类结果.2 相关工作近年来兴起的网络嵌人的研究起源于自然语言处理领域的表示学习[ 1 2 ], 该类问题的研究可以追溯到谱图理论[1 3], 社交维度学习[1 4]等研究. 随着该领域的发展, 很多网络嵌人的方法都旨在建模节点的相似性. 谱网络嵌人方法和谱降维方法相关, 例如快速近似谱聚类方法[1 5]和拉普拉斯特征映射方法[1 6].受word2vec模型[1 2]的启发,一类基于skip gram模型的方法被提出, 并有很好的性能, 例如DeepWal k?、LINE[ 4]、node2vec[ 5 ]、 metapath2vec[ 6 ]等模型. 最近,受词嵌人问题转化为矩阵分解的启发[ 1 7 ], 文献[7]指出基于skip gram这一类的方法可以转化成矩阵分解问题. 通过将随机游走的过程建模成矩阵的乘法, 然后在近似的高阶矩阵上做奇异值分解, 可以得到网络节点的低维表示. 并且, 其中提出的NetMF方法在设置较大窗口大小参数时可以得到高质量的网络嵌人, 基于它再做网络节点多标签分类时表现出比使用DeepWal k和LINE更好的性能?除了文献[7]的NetMF方法外, 其它基于矩阵分解的网络嵌人模型还包括GraRep[ 1 8 ]、HOPE[ 19 ]、TTADW[ 2 <^tIDHPE[ 2 1 ], 其中GraRep模型考虑整合高次相似度矩阵来获取节点的相似度信息, 但巨大的计算量和内存开销限制了其在大规模网络上的应用, HOPE模型可以应用于有向图的场景, TADW模型可以应用于节点带有特征信息的数据, DHPE模型可以应用于动态网络的场景. 最近, 也有几个NetMF方法的改进算法被提出. NetSMF[8]通过引人谱图稀疏化方法使得模型可以运行得较快, 不过仍然需要较大的运行内存. Pr〇NE[ 9 ]方法通过交换随机游走和矩阵分解的过程, 先对稀疏矩阵分解得到节点的低维表示, 然后再对节点的低维表示做信息传播增强, 这样大大降低了整体的计算复杂度. 然而, 在后续使用节点低维表示的应用任务(如多标签分类) 中, ProNE的性能很不稳定, 往往比NetMF的结果差.3 技术背景在本文中, 为了方便描述算法, 我们采用Matl ab450 计 算机 学 报 2021年所使用的方法来指定矩阵的部分元素.3. 1 奇异值分解和特征值分解矩阵AeR?x"的奇异值分解(SVD) 可以表示为A=USVT(1)其中[/=[M!, M2,…]和V=[W!, ,…]是分别包含左右奇异向量的正交矩阵. 对角矩阵z包含了矩阵A的奇异值(的, 内,…) ? 设队和1分别是[/ 和V的前々 列, 对角矩阵厶包含矩阵A的前& 个最大的奇异值, 矩阵A的截断SVD可以表示为人, 即A^At=UkSkVl(2)其中At也是初始矩阵A的最佳秩& 近似[ 2 2 ].若A为对称矩阵, 它存在如下形式的特征值分解( EVD) :A=UAUt(3)其中yi 为对角阵, 其对角元为A的特征值, 正交矩阵[/ 的各列是A的特征向量. 由于实对称阵的特征值均为实数, 只需将式( 3) 中A的负对角元取相反数、 然后将C/T的相应行也取相反数, 式(3) 即可变成A的奇异值分解, 其中[/ 的各列是A的左奇异向量.类似于截断奇异值分解, 由式(3) 也可以得到截断特征值分解:=UhAhUTh(4)其中对角阵儿为Zl X 的对角阵, 对角元为/! 个绝对值最大或代数值最大的特征值, 队为[/中与这些特征值相应的特征向量组成的矩阵. 计算截断特征值分解的传统算法为ARPACK算法[2 3], 其具体实现包括Matl ab中的eigs 命令和Python 的eigs、elgsh命令等, 它们特别适合处理稀疏矩阵.3. 2 基于矩阵分解的网络表示本文的主要目的是提出一种NetMF算法的改进版本, 它能够显著减少NetMF算法的内存用量和计算时间. 由于NetMF算法是针对无向图的网络嵌人方法, 我们提出的方法也只考虑无向图即对称稀疏矩阵. 我们用G=(y, E, A) 表示一个无向网络, 其中V表示顶点集, E表示边的集合, A表示G的邻接矩阵.网络嵌人的目标是学习到一个投影, 该投影可以映射每一个顶点到一个々 维向量( 々■<<?) ,使得可以保存它的结构属性信息, 进而这种网络表示被提供给后续的网络分析使用, 例如边预测和节点分类等.最近, 基于矩阵分解的网络嵌人显示出它在网络表示上的优越性. DeepWal k 是一个近年来被广泛承认的网络嵌人模型, 随机游走的长度对DeepWal k模型的实验结果有影响. 该参数越大, 随机游走得越远且更多较远的点也会被认为是当前节点相似的节点, 但一定程度上也相当于放宽相似性约束, 可能会引人一些噪声, 因此如何设置这个参数使得实验结果更好并没有普遍适用的结论. 文献[7]揭示了当DeepWal k里的随机游走的长度达到无穷大时, 它相当于是对矩阵trunc_l og° (V〇[(qG)(D^AYD1j( 5)作分解, 其中1:]: 11 11£;_1 (^°表示矩阵的每个元素和1取最大值后再取l og, 即trunc_l og〇( :r)=l og( max(l , :r) )( 6)式(5) 的参数D为邻接矩阵A生成的对角阵, 其对角元I , tW(G)二D, 而参数g和参数6 分别表示窗口大小和sklp gram模型里负采样的大小. 在下面的工作里, 我们考虑带有较大的窗口大小的情况, 比如DeepWal k 默认的情况下<7=10.文献[7]提出的NetMF给基于skip gram的网络嵌人方法奠定了理论基础, 使得网络嵌人模型有更强的可解释性. 算法1 描述了处理较大窗口的NetMF算法[ 7 ]_算法1.NetMF.输人: 邻接矩阵Aei rx", 特征值截断参数fe, 奇异值截断参数h窗口大小g输出: 网络嵌人BeR-x*1.截断特征值分解: £>2. 构造矩阵M=D"21/*(公71: ;)1/加"2r13. 计算M=trunc log。(V〇|^G)jVf)4. 截断奇异值分解: M?队ur5.返回£=仏对/2然而,当直接应用NetMF算法到大规模的数据集上时存在一些问题. 首先, 在算法1 第1 步, 对矩阵ir1 / 2AIT1 / 2做截断特征值分解, 但直接计算特征值分解需要很长的时间. 算法1 的第2、4 步也需要花费较多的时间, 且第2 步存储大的稠密矩阵M是很有挑战性的. 比如, 当网络节点数《为110 万时, 稠密矩阵M的存储量超过8 TB, 这使得该算法很难应用到大型网络分析当中.3. 3 随机化奇异值分解有关技术基础的随机化奇异值分解算法[ 1 °]可以用来计算近似的截断SVD, 该算法如算法2 所示.算法2. 基础随机化奇异值分解.输人: 矩阵Aei irx ", 奇异值截断参数I幂迭代参数户, 过采样参数^谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 45 13 期输出:1. X2=randn(n,々 +s)2.g=orth(AX2)3. FORf=1,2,…,>DO4. G=orth(ATg)5. g=orth(AG)6. ENDFOR7. B=QrA8. [ U, U]=svd(B)9. U=QU10.U=U( t at k) ,S=S(l t kAt k),V=V( t y l t k)在算法2 中, 12 是一个高斯随机矩阵, 参数s使得采样矩阵12 超过& 列以获得更好的计算结果. 矩阵2的列包含了A列空间的主要基, 因此A?2B=22ta, 然后对一个a+dXw大小的矩阵b使用SVD, 就可以得到矩阵A的近似截断SVD. 算法1的第3?6 步为幂迭代技术[1 °], 应用它之后相当于计算矩阵C4AT)1的奇异向量, 由于C4AT) 1的奇异值衰减比原始矩阵A快得多, 使用幂迭代后再做随机化奇异值分解可以使结果更接近最佳秩& 近似.幂迭代过程中的正交化〇rth( ) 可减轻浮点数计算的舍人误差影响, 这个正交化操作通过QR分解来实现. 随机化奇异值分解算法在很高概率下能保证:A QQTA=A USVT<( l +e)A At(7)其中At是矩阵A的最佳秩々 近似,e 是一个误差阈值.对于实对称阵AeR"x", 对算法2 稍作修改就可以得到截断特征值分解[ 1 °]. 此时算法2 中的矩阵2表示了A的行空间和列空间的主要基, 因此:A^QZQT=QQtAQQt(8)对实对称阵z=2TA2做截断特征值分解, 然后将分解结果代人式(8) 就可以得到矩阵A的近似截断特征值分解.应当指出, 由式( 8) 得到的算法相比基于A?22ta的算法其低秩近似效果差一些. 对于对称矩阵, Tr〇PP等人最近提出了基于22TA形式的近似、且保证结果仍为对称矩阵的方法[ 2 4], 它对原矩阵的近似程度更好. 基于算法2 得到的矩阵2、b, 即得到原矩阵A的近似矩阵A=2B, 文献[24]指出:Asym=^(A+AT)=^(QB+BtQt)(9)为对A近似程度更好的对称矩阵. 根据文献[25] ,Asym是A到所有《 阶实对称阵形成的凸集上的投影, 由于A本身也在这个凸集内, 则根据文献[26]^■定有:IA Asym| | f<IA AIF( 10)并且, 对Asym再做低秩近似得到的结果也比A的结果更准确[ 2 4].此外, 文献[27]提出了一种单遍历奇异值分解算法, 它在数学上与幂迭代参数f=〇 的算法2 等价, 但只需要对矩阵A访问一遍, 特别适合于在内存受限的情况下处理大型的稠密矩阵、 或者高效率地处理流数据. 针对大型稀疏矩阵, 文献[28]提出了高效率的随机化SVD算法, 它与算法2 在数学上等价, 但使用了多种加速技巧可使得对实际大型稀疏矩阵的处理时间缩小9 倍. 这些加速技巧主要包括:( 1) 利用特征值分解来快速计算细长条矩阵的SVD和QR分解, 即使用elgSVD算法[ 2 8 ].(2) 在幂迭代过程中, 每隔一次矩阵乘法之后再做正交化操作.( 3) 幂迭代中可使用LU分解替代QR分解.4 基于高效矩阵分解的网络嵌入方法在这一节, 我们首先给出利用随机化矩阵分解技术提高NetMF方法处理大型网络的效率的主要思路, 然后依次提出针对稀疏实对称阵的快速随机化特征值分解、矩阵M的高效率构造与隐式存储以及快速单遍历奇异值分解这三项技术, 最后给出算法eNetMF的完整描述, 并做计算量分析.4.1基本思想可粗略地将NetMF方法分为三个主要步骤:用截断特征值分解归一化网络矩阵来近似矩阵、 基于特征值分解构造高次近似矩阵M、计算M矩阵的截断奇异值分解. 对于大型网络, 第一步和第三步都无法使用传统的矩阵分解算法来实现, 它们需要巨大的运行时间, 而第二步不但有很大的计算量, 而且形成的稠密矩阵造成巨大的内存开销, 也给第三步的执行带来困难.首先我们可以使用随机化特征值分解算法来代替NetMF方法的第一个主要步骤, 在几乎不损失准确度的情况下减少其计算量. 其次, 为了解决大型稠密矩阵M或M给内存量带来的挑战, 我们提出高次近似矩阵的高效率构造方法以及不显式存储M和M, 然后采用单遍历随机化SVD算法近似计算奇异值分解的思路, 这样极大地减少了整个算法的内存用量.同时我们还提出快速、 准确的单遍历奇异值分解技术保证最终网络嵌人的结果有足够的准确度.45 2 计 算机 学 报 2021年本文提出的eNetMF算法的流程图如图1 所示, 图中上排实线框表示本文提出的eNetMF算法输入图G=(F, E, 』)At股主要步骤, 下排虚线框表示NetMF箕法的主要步骤?网络嵌入的结果#[0.321,0.771,-0.189]厲1eNetMP^_, 雜爾靡眞(下排虛线: 框; tNetMf算中相霞敵步4.2 针对稀疏实对称阵的快速随机化特征值分解我们将文献&8]: 輕出的适用于稀疏矩阵加速分解的技巧与文就[241提出的对称矩阵随机化特征值分解算法锫脅. , 餐到算法丄其中,l u表示对矩阵做LU分解.算法3.快速随机化特征值分解(frgigs>.:输人:艇阵A6: ,", 特狼值戴断参数是, ■迭 蠢数6过意導参数输坶5 c:ei r%灰£ ;4*1.randn(n,^ + 5)2.Y=AQ3.[Q,?,?]=eigSVD(Y)4.FORf =l,2,?? ?, 夕DO5.IFi<pTHEN6.[2,?]=lu(A(A?)7.ELSE8.[2,?,?]=eigSVD(A (A?)9.ENDFOR10.Z=lQ,AQ]11.[i>, T]=qrCZ)12. 乃, :r2 分别是矩阵:r的前6+5 列和后a+5 列13 .S=(T1t!-\-T2tD/214.[U, y]=eig(S>15 .ind为A中A 个最大的特征值的位置索引集合16.U= PlK:yind),A=A(ind,ind)震鑛4的第:l〇?14#裹于如T推导* 斑于— —=Y(2B+BTQT?=yCS> BT][2TJai)如杲对二[232]做精简'的QR分解5[Q. B1]=Ptr!, T,J(12)其中P为列班交阵,[A,T2 ]为上三角方阵且T: 和1^维度一样, 则:-(PT.f--(PT1)T- yP(: t1 tJ+tz tDptas)记s (i?+r2if), 对s作特征值分解?苒代入式(13) 即得到 的值分解, 进而得到雇矩哞A的近似特怔值分解下面进行算法计算量微空间开销的分析. 设/=是+ “隸法3的第2步的浮.点运箕欲_是〇(:前*U)/),ww(A)为A中#零元素的数I根据文献[28], 第3^發步的浮戾运箅次纖、为0(左( ?z /2+_多(皮)i ,篇10 步蠻裏 +W锻U) D次浮逼: 貧雾, 簾11?16 步鄉需要 +?/2} 次浮点运算? 逋常情况下, /远小于网络顶点数 算法3 的浮点运算次数为0(扒《?元4) /+?产))? 考虑到幂迭代参数p与过采样参数s 均为不大时常数, 商由f大规模两络的稀疏性, wm(A)也本超过》 的某个常数倍| 箕法3的时间复杂度为〇( rt肢(A从-I-邊2),, 其中灸 为特怔值截断参数. 这与Matlab 中eigs命奢的复獻 卷,钽由于随机化算抜中的运算更适合于当前的计算机体系绪构, 算法3 的运行时间比eigs 显著缩短, 后面的实验结果将發证这一点, 此外,: 上述分析也表明算法3 的时间复杂度与矩阵规模呈线性关系.在全间复杂度方商, 矩阵A采用稀疏矩阵方式存储*而算法渉及的稠密矩阵维数都不超过 或所以算壤3_空间愈觀愈为〇(>??£(▲; )+喊),也与矩阵规模呈栽性关, 系.4. 3 矩阵M的高效率构造与隐式存储義NetMF#法中, D1 /2AD—1 /2的#征償范圈'在[1,1] 賴内w, 对于大型矩阵来说这意味着该谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 45 33 期矩阵的奇异值衰减趋势比较缓慢. 随机化算法在处理奇异值衰减缓慢的矩阵时, 得到计算结果的近似误差较大. 为了缓解它给矩阵近似准确度带来的问题, 我们提出在保证算法1 第2 步矩阵M不变的同时修改计算截断特征值分解的矩阵, 通过对一个奇异值衰减较快的矩阵计算截断特征值提高准确度.具体地:qq(D^AYD1=D1 +aDA((D1A)r 1)D^D1 +ar1「1(14)其中 ( o,i). 如果对矩阵 执行截断特征值分解, 即DADa^GhHhGj( 15)将式(15) 代人式(14) 当中, 得X)(D^A) ^1^D1 +a(GhHhGj+r l1 +2 aG+…+GhHhGj-D^G.H.GDD1 ^q=D1 +aGhHh(YjKr^)GlD1 +a(16)r 1其中1 +2 aGAHA, 为一个AXA 矩阵. 由于/K<w, 计算矩阵K及( 16) 中它的各次幂花费的时间很少.因此, 可以将算法1 中的矩阵M替换为:qM=D1 +aGhHh(Kr1)GThD1 +a( 17)r1这样, 选择合适的《可使矩阵DiADi的奇异值衰减较快, 从而使用算法3 能比较高效、 准确地得到其截断特征值分解, 也不损失NetMF方法中矩阵M的准确度.为了避免存储稠密矩阵M或M, 我们提出一种隐式存储方案, 即考虑分解式M=FCFT, 其中_F=D1 +?GA , C=i^( f;ir〇, 然后分批计算出M的r 1行, 利用下面将介绍的单遍历SVD算法计算其截断奇异值分解, 由于它只访问矩阵M的元素一遍, 对计算出来的M的若干行处理后即可将其删除, 因此可大大节省内存用量. 而需要存储的矩阵FeR"XA,(^肢以^远小于两^肢^的规模.4. 4 快速准确的单遍历SVD算法我们首先提出一种简洁的单遍历SVD算法, 它与文献[27] 中的算法等价, 但构造 近似矩阵的操作更简洁, 运行效率更高, 如算法4 所示. 其中, A,表示输人矩阵A 的第z 行, 通过步骤4?7, 我们可以得到两个包含原始矩阵A信息的小矩阵Y和W,它们保存了矩阵A的行、 列空间的主要成分, 基于它们可以进一步计算A的奇异值分解.算法4.一种更简洁的单遍历SVD.输人: 矩阵Aeirx", 奇异值截断参数h过采样参数^输出:, vei rx*1.X2=randn(n,是+ 5)2.y=[ ]3.W=zeros(n^ + 5)4.FORz=1,2, ? * ?DO5.y= AQyy=[y;j]6.W=W\ AI'y7.ENDFOR8.[g, R]= qr〇〇9.B=RTWT10.[U, U]=sVd(B)11. U= QU12. U= U( t Atk),S=S(ltk,ltk), V= V( t yltk)在算法4 中, 步骤8?12 是具体计算矩阵A的奇异值分解的过程, 它不同于现有的单遍历SVD算法[2 7]. 定理1 表明算法4与不做幂迭代的算法20=〇) 在数学上是等价的.定理1.在算法4 中得到的2的各列是AX2列空间的单位正交基, b=2ta.证明. 根据算法4的第4?7 步, 我们得Y=AX2, 再根据第8 步, 对Y执行QR分解, 因此得到的2的各列是AX2 列空间的单位正交基.下面再证B=2TA, 由算法4 的第4?7 步, 有再根据第9 步,B=RTWT=Rt(AtA£2)t=RtQtAtA=(Af2J?^)TA.又因为 得 , 将2代人上式, 得B=QTA.证毕.文献[27]中的单遍历SVD算法与不做幂迭代的基础随机化SVD算法(算法2) 在数学上是等价的, 故定理1 也表明算法4 与文献[27]里的单遍历SVD算法也是等价的.对于实对称矩阵, 文献[24]提出的技术可以保证得到的低秩矩阵也是对称的, 从而提高结果的准确性. 将它与算法4 结合, 得到算法5.算法5. 针对实对称阵的单遍历SVD.输人: 矩阵M6R"x ", 奇异值截断参数h过采样参数^输出: t/eR"x*, 從R*x*R"x*1.n=ranAnin,k\s)2.y=[ ]3.Vy=zeros(n,是+ 5)454 计 算机 学 报 2021年4. FORz=1 , 2, ? * ? DO5. :y=MW, y=[yj]6. W=W\ Mjy7. ENDFOR8. [ 2, R]=qr 〇09. Z=lQ, WR1^10.[P, T]=qr(Z)11.Tut分别是矩阵T的前A+s 列和后A+ 5 列12.S=(I\ Tl \ T2 Tj')/213 .[&, A]=eig⑶14.i nd为A中&个绝对值最大的特征值的位置索引集合15 .r/=P&(:,i nd), S=abs(A(ind,ind) )16 .V= r/sign(A(ind, ind) )算法5 的第9 步是由于, 根据算法4 , 我们有B=RTWT, 则式( 12) 中的[2, BT]=[AWR1]? 第14?16 步与算法3 不同, 是由于这里要求奇异值分解,所以需保证Z的对角元非负.4.5eNetMF算法与相关分析结合算法1、3 和5, 我们得到基于高效矩阵分解的网络嵌人算法eNetMF, 如算法6 所示.算法6. 基于高效矩阵分解的网络嵌人方法(eNetMF) .输人: 矩阵AeiTx ", 特征值截断参数fe, 奇异值截断参数h批处理大小参数^过采样参数^归一化参数a输出: 网络嵌人BeR"'1. 用算法3 计算截断特征值分解2. ifMK=GlD1 +2"Gt Ht3.计算F=D1 +-G4以及C= fl*( f;iT”r14. >T3=randn(n,是+ s)5. y=[ ]6. W=zeros(n^ + 5)7. FORf=1,2,. . .,n/r?DO8. F} =F\^iv u+l:ivj:]9. M, fi=trunc  log°(V〇|^G)F, CFT)10.y=M, n, Y=[Y;y^11.ENDFOR12. 执行算法5 的第8?1 5 步13.E=USm算法6 的第1 步使用算法3 实现, 对中小规模网络《可以取1 /2 , 对于大规模网络可以通过试验得到更合适的取值, 从而提高运行效率、减少近似误差. 第2?12 步实现了矩阵M和M的隐式构造, 并对M的行进行批处理的单遍访问, 为后续计算截断SVD做准备. 这里, 为了算法描述简洁、 且不失一般性, 只考虑了〃能被n整除的情况.下面分析算法6 的计算量和空间开销, 设/=々+二第1 步的时间复杂度为OC wwzUH+M2) , 空间复杂度均为0( wwzU) +舫) ? 算法6 的第2、3 步包含oc np) 次浮点运算, 第7?12 步包含ocva+z) )次浮点运算, 第13、14 步的浮点运算次数为0( nZ2+Z3) . 由于《远大于其它参数的值, 算法6 总的计算复杂度为〇(?2a+/) ) . 在空间开销方面, 第1 步需要的存储量是〇( wwz(A)+M) , 在后续计算步骤中,需要存储的矩阵尺寸都不超过wX/^wXZ 或wXw,考虑到矩阵A在后续不再使用, 算法6 的空间复杂度为0(w(/i+ Z+w) ).可以看出, eNetMF算法在空间复杂度方面大大优于NetMF算法. NetSMF算法[8]的空间复杂度为0(叫.期2〇4) ) , 其中£:一般取值1000 或者10000 ,因此我们的eNetMF算法在内存用量方面也显著小于NetSMF算法的内存用量. 由于eNetMF的时间复杂度仍为〇(?2a+/) ) , 它处理特别大的网络时会花费过多的计算时间, 将来可以考虑采用分布式并行计算等方式来加以改进.5 实 验本文算法均使用c语言编程实现, 其中用到的矩阵计算和QR分解、LU分解、SVD分解等算法通过调用IntelMKL的库函数进行实现, 同时采用OpenMP编程实现了多线程计算. 所有实验均运行于装有32核Intel( R)Xeon(R)CPU、256GB内存的Lmux工作站上, 实验结果中的时间均为32 线程并行计算的实测运行时间.下面我们首先介绍测试的网络数据, 然后验证第4.2 节提出的特征值分解算法freigs 的准确度与有效性, 最后通过多标签分类的实验验证eNetMF算法的优势, 并给出更多实验结果.5. 1 数据集我们选择如下5 个网络数据集来进行测试.( 1) PPI[ 2 9]. 该数据集是一个蛋白质和蛋白质交互的网络子图, 数据集里节点的标签是从标志性基因集获取的, 可以表示生物学状态.( 2)Bl 〇gCatal 〇g[ 3°]. 该数据集是一个线上博客主的社交关系的网络, 其中节点标签表示博客主的兴趣.( 3) DBLP[3 1]. 该数据集是一个学术引用网络,网络中的节点是作者, 标签是他们所活跃的会议.( 4)Fl 1 Ckr[ 3 °]. 该数据集是一个FHckr 网站上的谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 45 5图25. 3eNetMF算法在多凇5. 3.1 实验参数设置与评价指标我们将本文提出的eNetMF网络嵌入方法与DeepWalk、NetMF、NetSMF、 ProNE四种方法进行对中给出的程序. 根据文献[7], 对于所有的方法在不额外说明的情况下都默认设置成窗口大小g=10、负采样参数 1 以及嵌入映射维度 128. 在200100 200 100 200Flickr200 400YouTube65遄4--eigs■■ ■■■ freigs嵙3#2、?10 100 200算塗软 Ugst函魏对归一化M翁雉阵酸_鑛斷特征偉聲觳_绪暴f、签分类问题上的效果比》 对比的程序是这四种方法的作者在文献Cl J邛]--eigs■■ …freigs3 期用戸黑相联系的网络, 标签代表了用.户的兴趣组.( 5)YouTube?. 读数据梟是一个视频分享网姑上的用户玄互网络, 用户的标签为他们喜致的视频的类型.其中*PPI 和BbgCatal og规模相对较/M旦是在网络嵌入方面的研究工作中被广泛使用* 而DBLP、Fl ickr 和Youfube的:规儀相对较: 大.这巻载摒集的一些具体倩息如表1 所示?表1 数据集的具体信息数据集名称 点个数 边个数 标签个数PPI3890 76 584 50BlogCatal og10312 333983 39DBLP 5 1264 127968 60Fli ckr 80513 5 899882 195YouTube 1 138 49929 90443 475.2 特征值分解算法freigs 的有效性计算截断奇异值分解的传统算法是ARPACK算法P3], Pyt: h_麗:&cipf 贈eigs、 eigsh涵敎慕基:于它t且使用Intel 的MKL实规的, 下面将我们的算法3( 即fmgs)与处理对称稀:疏矩阵的rigsli函数做比较, 后者也就是Ne'tMi*8中所使用的.测试的矩阵是由表1中^个数据梟鲁到的矩阵,除了对DBLP 和YmiTtAe 我们分别睫c?=d.r邦 d. 玆5 外, 对其它:数摒囊我们都设a值PPI为缺省的〇._?!齿了与后?面的网络嵌人实验保持一致, 对PPI、Blc^Cstsl 〇f、DmfnY轉 这4个数据集4寺征值截断参数6=256, 对Fli ckr 我们取々=512. 对于華迭代参数和过采祥参数餘了DBLP、Flickr 外都取多=IQ?s=5: 6.Fl ic. kf 对应:餘_障载稠密、 且特征植. 截断参数较大, 我们取f=8y=10(VDBLP对应的蔚一化网络矩阵特征值下降缓慢, 我们取f=16y=256. 我们的算法3( freigs箅法)与eigsh的运行时间列于表2中. . 从中可看出,随机化特征值分解算法在: 大数据.集上比传统算法快接近10 倍.表2算法3(freigs) 与ei获h 的运行时间比较 (单位: 5)数据集名称 eigsh freigs 加速比PPI 3. 0 0.7 4.3XBlogCatalog11. 01. 95.8XDBLP 81. 0 9. 0 9. OXFlickr 415. 079. 05.3XYouTube 1320.0 138.0 9.6X图2 显示了算法3 和eigsh 计算出的最大特征值曲线? 从中可以着:出, 两'者的结果几乎是不可区分的, 这反映出随机化待征値算法freigs有较圩的准确度?通过铃_多标:盤分类问题上的实验结果, 我们也可以看出freigs算法每到的截断特征值分解几乎不会影响网络嵌人的性能.DBLP BlogCatalogfft^.3.3..0. 8j.4l.o.o.o.456 计 算机 学 报 2021年NetMF和eNetMF算法中, 对归一化网络矩阵作截断特征值分解的参数/i 基本上都取值256, 只是对Flickr令512.对于DeepWal k算法, 我们按照文献[3]的作者建议的参数进行设置, 即随机游走的长度取40 , 每一个点的游走数量取80 以及窗口大小的参数取10.对于NetSMF算法, 需要设置网络稀疏化的非零元参数M. 我们和文献[8]保持一致, M的值几乎都是103X gXwwz(A) /2, 只有对Bl ogCatal og, M=104X,qX, nnz(A)/2.对于ProNE算法, 我们和文献[9]设置相同的参数, 即切比雪夫扩展次数为10, 拉普拉斯算子里的"=0.2,6=0.5.对于eNetMF方法, 除了在5.2 节已经介绍的.?参数和进行第一步快速随机化特征值分解所需要的幂迭代参数、过采样参数外, 还需要设置逐行遍历矩阵M的批处理参数W和最后单遍历奇异值分解中使用的过采样参数^批处理参数n影响内存开销和矩阵乘法的计算时间, 较大的?会使得矩阵乘法加快, 但也导致峰值内存用量较大. 我们对大多测例使用w=3200 , 而对于最大的YouTube 设置w=12800. 对最后的过采样参数, 统一取5=100.在上述各种方法得到网络嵌人后, 与文献[3,79]一样我们将其应用到多标签分类问题上, 通过分类的准确性来评价不同网络嵌人表示的性能. 对各个数据集, 我们随机采样一部分的带标签节点作为训练数据, 剩下的作为测试数据_ 对于PPI 和Bl ogCatal og,训练节点所占比例从10 %起每次增加10 %递增到90%, 总共进行9 组节点分类的实验. 对于DBLP、Flickr 和YouTube, 训练节点所占比例从1%起逐渐增到10%, 共进行10 组节点分类的实验. 在实验中, 我们使用由LIBLINEAR[3 2]库实现的一对多的逻辑回归模型进行多标签分类. 在测试阶段, 逻辑回归模型生成排序的标签、而不是确切的标签分配, 为了避免阈值效应, 我们假定对于测试数据, 标签的数量是给定的[ 3’33 ]. 对于每个实验, 我们重复预测10 次,然后观测不同网络嵌人方法得出的平均Ml cr〇 _Fl、平均MacroFI 指标[3 4]和准确率指标[3 5]. _F1 分数指标的定义为F12PRP+R(18)其中P表示精确率,i? 表示召回率. 计算Micro FI时, 先将所有类别的真正例数量( TP)、假正例数量(PT) 和假负例数量(FN) 相加得到总体的TF、TW、值以及总体精确率P和召回率犮.TP二 ̄TPelas;s l ̄ ̄I-TPda ss2  ̄ ̄I-.+TPclas s」 v( 19)FP:二FPchs; s l ̄ ̄I-FPdas s2 ̄ ̄I-? ? ?FPcl as sJ"v(20)¥n二二FN如;si+FNc\&^2+* ? ?+FNcla ssw(21)tpP== ̄=(22)TP+FP-fpR=__(23)TP+FN然后, 类似式(I8) 计算Micro FI:Mi cro FI2PRP+R(24)计算Macro FI 时, 则是分别计算每个类别的F1 分数, 然后求平均:Macro FI=FIclas sl ̄ ̄t-? ? ? ̄ ̄t-Flclass NN(25)在计算多标签分类的准确率时, 我们先计算一个节点的多标签准确率为预测正确的标签除以总共的标签数量, 然后取整体的分类准确率为所有节点的平均:AccMrac^=(26)nti| i,U> 5.I其中T, 表示正确的标签集, S, 表示预测的标签集.5.3.2 实验结果图3 和图4 显示了不同网络嵌人算法在5 个数据集上进行多标签节点分类的性能.其中, 由于所需内存超出了256GB, Net SMF对Fl i ckr和YouTube的实验结果无法获得, 而由于同样的原因NetMF对YouTube 的结果也无法获得. 从图3 和图4 可以看出, 无论是Macr〇_Fl还是Mi cro _F1, 使用eNetMF算法后的结果都与使用NetMF得到的一致(尤其在训练比例较大时) , 这说明本文提出的改进NetMF算法的技术并没有给网络嵌人的质量带来明显的影响. DeepWal k方法在PPI、Bl ogCatal og、DBLP和YouTube 上有和eNetMF差不多甚至更差的效果,仅在FUckr上要好于我们的方法. ProNE方法虽然在某些数据上得到的Ml cr〇Fl 值最好, 但在所有测试数据上其得到的Macro FI 值明显比其它方法的差, 这说明ProNE得到的嵌人表达没有包含图中足够的信息, 因此对一些标签较少的节点分类效果不够好.网络嵌人算法在多标签分类问题上的准确率结果列于表3 中. 我们记录当训练节点所占比例为60%时的PPI 和Bl ogCatal og 的准确率结果, 以及当训练节点所占比例为6%时的DBLP、 FUckr 和YouTube 的准确率结果. 从表3 的结果可以看出, 我们的方法和NetMF的效果差不多, 在所有数据集上与其它对比对象比较均有差不多或者更好的准确率.谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 45 7 3 期训练比例/%Fl ickr YouTube图3 使用不同网络嵌人算法后进行节点多标签分类得到的Marco-Fl 值(横轴为训练数据所占的比例)PPI BloeCataloe^-DeepWalk-?-NetMF备NetSMF+ProNE ̄t—eNetMF20 4060训练比例/%8030L20DeepWalk夺NetMFNetSMF^ProNEeNetMF406080训练比例/%DBLP40Youtube^DeepWalk-?-NetMF各NetSMF斗ProNE十eNetMF4训练比例/%10-^DeepWalk-?-NetMF各NetSMF+ProNE ̄i—eNetMF46训练比例/%10训练比例A庫. 傳兩不■ 翬儀A#■翁嫌行节属_签#: _飼的MteiFl疸1猜轴为刺馨敷.腐古鋒比例)表3各种网络嵌入算法的多标签分类准确率(筚偉数据集名称 DeepWalk NetMF NetSMF ProNE eNetMFPPI17. 082 18. 02018.621 18. 985 18.148BlogCatalog40.14341.1 1839.36139. 529 40.958DBLP 58.280 59.9 19 59.287 55.527 58.352Fli ckr34.35 133.173 N. A.33.48533.080YouTube 98.247 N. A. N. A. 98. 289 98.256各种网络嵌人算法的运#时间列于表4 中, 所有算法对应的程序都是适含fl32 线程运行的并行程序?且对间包括了读取数据文件的时间? 从表.4可以看出,ProKE算:法的运行时间最親dNetMF算法在矩阵规模不大的时候, 速度也比较快. 在Flickr 数摈上其相对于NetMF 的加速比高达41 倍. 而MeflSlvIFS: 然在; 处理DBLP时也比NetMF耗时■?钽在处理更大例子时由于内存蕾求太大而无法运行. De仲Wal k算法是所有对比对象里运行时间最夂的,esMeBvIF算驗相对"于D?pW?ilk 算法翁每个数磨集上的加速比都要超过2〇倚.表4 各种网络嵌入算法的运行时间 (筚偉,.s)'数据:集舊猶DeepWft?Net?tN8I獅PJfljNE.eNe爾f 加速比PPI318 14 19 1.4 1.5 9.3XBlogCatalog816 84 1140 5.0 4.6 18.OXDBLP 4540 632 82 11. 039. 0 16. OXFlickr 79206120 N.A.72.7 150 . 041. OXYouTube 108015 N. A. N. A.194.3 4852. 0—458 计 算机 学 报 2021年对于NetMF、NetSMF、ProNE和eNetMF这四种算法的峰值内存用量列于表5. 从中可以看出,对Fl i ckr 数据eNetMF的内存用量仅为NetMF的1/46. 处理最大的YouTube 数据,eNetMF 只需120 GB内存即可算出网络嵌人, 并得到非常好的网络节点分类结果( 如图3、 图4). 虽然在运行时间和内存用量上, 本文的方法不如ProNE, 但是如前面所展示的, 本文方法在多标签分类结果的效果上更稳定、更好.表5 各种网络嵌入算法的峰值内存用量(单位: GB)数据集名称Net MFNetSMFProNEeNet MF 缩小倍数PPI0. 396. 860. 160. 291. 3XBlogCatalog2. 20135. 000. 460. 554. OXDBLP31. 0018. 200. 722. 0016. OXFlickr182. 00>2565. 504. 0046. OXYouTube>25 6>25 612. 00120. 00对eNetMF算法各部分的运行时间进行详细统计后发现, 第一步随机化特征值分解和最后的单遍历奇异值分解所花费时间占比例很小, 而两者之间的矩阵计算部分(算法6 的第7?12 步) 消耗时间最多. 例如, 对YouTube 数据, 矩阵计算部分花费的时间为4574 s, 占总运行时间90%以上, 而单遍历奇异值分解的时间仅为35s. 对于该数据, 我们还比较了算法6 中的单遍历奇异值分解与文献[27] 中的单遍历奇异值分解算法, 后者的运行时间为1434s, 可见我们提出的简洁单遍历算法与保证分解结果对称的技术显著加速了计算、也有很高的准确度.5.4eNetMF算法在边预测问题上的效果5. 4.1 实验设置与评价指标我们将本文提出的eNetMF 网络嵌人算法和DeepWal k、NetMF、NetSMF、 ProNE在网络的边预测问题上进行比较, 这些方法的参数设置和5.3 节所介绍的一致. 边预测问题旨在基于现有的网络结构来预测可能存在的边. 在我们的实验当中, 我们随机地抽取原始图30%的边作为测试集, 剩余70 %的边作为训练集. 首先将不同的算法在训练集上进行学习得到训练集的网络嵌人结果, 然后根据网络嵌人结果来计算每一个在测试集的点对(M, W) 上的相似度分数, 最后采用广泛使用的AUC指标[ 5 ]来评价边预测质量的好坏. 在上述过程中, 计算点对(M, W的相似度分数可以按照点对U, W对应的嵌人向量的内积、余弦距离或欧式距离来计算, 也可以使用边特征方法[ 5 ]来计算. 对于每个网络嵌人算法,我们选取使其AUC指标结果最好的相似度分数计算方法并记录AUC的结果.5.4.2 实验结果各种网络嵌人算法在边预测问题上的AUC指标的结果列于表6 中. 从表6 可以看出在PPI 和Flickr数据集上eNetMF算法比DeepWal k、ProNE要差, 但在数据集Bl ogCatal og、DBLP和YouTube上, eNetMF算法的结果比其它方法好或差不多. 整体来看, eNetMF的效果和NetMF的效果相比差不多甚至更好, 特别是在DBLP数据集上, eNetMF算法显著更好, 这是因为DBLP的归一化网络矩阵的特征值衰减非常缓慢, NetMF算法里的elgsh函数在不设置迭代次数的时候很难收敛, 而设置了迭代次数的特征值计算的结果有一定的误差, 故该数据集的结果也验证了本文第4.3 节提出的矩阵高效率构建方法的有效性. 边预测实验验证了eNetMF算法具有很好的推断预测的能力, 这得益于我们的模型和NetMF—样, 较好地保存了网络的结构信息.表6 各种网络嵌入算法在边预测问题上的AUC值数据集名称DeepWal kNet MFNetSMFProNEeNet MFPPI0. 7430. 7370. 7640. 7970. 735BlogCatalog0. 8800. 8780. 8830. 8860. 876DBLP0. 8480. 8570. 8480. 8450.916Flickr0. 9230. 879N.A. 0. 9260. 871YouTube0. 779N.A. N.A. 0. 8050. 8056 结论与展望本文在网络嵌人问题上, 提出了一个基于高效随机化矩阵分解的网络嵌人方法, 该方法显著减少了NetMF[7]模型的内存开销和运行时间. 本文首先提出了一种快速随机化特征值分解算法, 用以加速归一化网络矩阵求特征值分解的速度, 该算法展现出相比传统的稀疏矩阵截断特征值分解方法近十倍的加速, 且几乎不损失精度. 然后提出了一种简洁的且适用于对称矩阵的单遍历奇异值分解算法, 利用该算法避免了显式存储稠密矩阵, 使得算法的内存开销跟矩阵维度呈线性关系, 适合于处理大规模网络数据. 最后, 结合以上技术, 提出了基于高效随机化矩阵分解的网络嵌人算法eNetMF, 并将其应用于实际网络数据, 基于得到的低维嵌人进行多标签分类和边预测. 多标签分类的实验结果表明,eNetMF在各个数据集上的评测结果均与NetMF得到的结果差不多, 显著优于NetSMF和ProNE等其它网络嵌人方法, 而且eNetMF方法内存用量小、谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 45 93 期运行速度快. 对于节点数超过1 百万、NetMF 与NetSMF由于内存需求太大无法处理的YouTube数据, eNetMF只需1.3 h 和120 GB 内存开销即可得到网络嵌人, 并进而获得很好的多标签分类结果.边预测的实验结果表明eNetMF算法也表现出与其它方法差不多甚至更好的性能.本文提出的方法, 虽然在运行时间上相比NetMF有显著的优势, 但其时间复杂度仍为〇cva+/) ) ,其中《为网络节点数目. 因此, 在它在处理特别大的网络时需要很长、 甚至不能忍受的时间. 后续我们将考虑用GPU并行计算或分布式计算对改算法进行加速, 使得它在保证准确的同时能够处理更大规模的网络数据. 其次, 本文通过随机化矩阵计算方法改进NetMF方法, 取得了一定的效果, 后续还可以研究随机化矩阵方法在其它大数据挖掘和处理问题上的应用, 期望在保证结果准确的同时减少算法的时间和内存开销. 此外, 对于本文实验中体现出的ProNE算法得到的网络嵌人结果不稳定的问题, 很可能是由于ProNE算法做了近似的信息传播增强, 导致在一些稀疏图数据上的表现较差. 这种信息传播过多导致的过度平滑问题最近也得到学术界的关注, 将来我们也计划针对该问题开展工作, 希望研究出既保证网络嵌人质量又具有非常低算法复杂度的网络嵌人方法.参 考 文 献[1]ZhangF,LiuX, TangJ, et al . OAG; Towardlinki nglargescaleheterogeneousentitygraphs//Proceedingsof t he25thACMSIGKDDInternat ionalConferenceonKnowledgeDiscoveryandDataMining( KDD) . Anchorage, USA,201 9;2585 2595[2]Hamilton WL?YingR,LeskovecJ. Represent at ion learni ngongraphs: Methodsandapplicat ions. IEEEData( base)EngineeringBul let in,2017 ,40 :52 74[3]PerozziB?Al RfouR?SkienaS. Deepwalk: Onli nelearni ngofsocialrepresent ations//Proceedingsofthe20thACMSIGKDDInt ernat ionalConferenceonKnowledgeDiscoveryandDataMining. NewYork, USA, 2014 :701 7 10[4]TangJ, QuM, WangM, etal. Line: Largescaleinf ormationnetworkembedding//Proceedi ngsofthe24thInt ernat ionalConferenceonWorldWideWeb. Florence? It aly,2015:1067 10 77[5]GroverA,LeskovecJ. Node2vec: Scalablefeat urelearni ngfornet works//Proceedingsof the22ndACMSIGKDDInt ernationalConferenceonKnowledgeDiscoveryandDat a[6]DongY, ChawlaNV, SwamiA. Met apath2vec: Scalablerepresentationlearningforhet erogeneousnet works//Proceedingsofthe23rdACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining. Hal ifax,Canada,20 17: 135 144[7]QiuJ , DongY, MaI I , etal. Networkembeddi ngasmat rixfactorization: Unifyingdeepwalk,line ,pte ,andnode2vec//Proceedingsofthe11thACMInt ernationalConferenceonWebSearchandDat aMi ning. MainaDelRey,USA,2018;459467[8]QiuJ , DongY, MaI I,etal . NetSMF: Largescale net workembeddingassparsemat rixfactorizat ion//Proceedingsofthe28t hInt ernat ionalConferenceonWorldWideWeb. SanFrancisco, USA, 2019: 150 9 1520[9]ZhangJ,DongY,WangY, etal. ProNE: Fast andscalablenet workrepresent ationlearning//Proceedingsoft he28t hInternat ionalJointConf erenceonArt if icialInt el ligence.Macao ,China,20 19; 4278 4 284[10]I l alkoN, Mart inssonPG, TroppJA. Findingst ructurewithrandomness: Probabilisticalgorithmsf orconst ruct ingapproximat emat rixdecompositions. SocietyforIndustri alandAppliedMat hemati csRevi ew, 20 11, 53 ( 2) : 217 288[11]DrineasP,MahoneyMW. RandNLA: Randomizednumericallinearalgebra. Communicat ionsoftheACM, 201 6,59(6):80 90[12]MikolovT, SutskeverI , ChenK, et al. Dist ribut edrepresentat ionsofwordsandphrasesandt heircompositi onali ty//AdvancesinNeuralInformationProcessingSyst ems. LakeTahoe, USA, 2013: 3111 3119[13]ChungFRK? GrahamFC. Spect ralgrapht heory. Providence ?RhodeIsland: AmericanMathemat icalSociety?1997[14]TangL, LiuI I . Relationallearningvia latentsocial dimensions//Proceedi ngsof t he15t hACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDat aMining. Paris,France, 200 9; 817 826[15]YanD, I l uangL,JordanMI. Fastapproximat espect ralclustering//Proceedingsofthe15 thACMSIGKDDInt ernationalConferenceonKnowledgeDiscoveryandDat aMining.Paris, France, 2009: 907 916[16]BelkinM, NiyogiP. Laplacianeigenmapsandspect raltechniquesf orembeddingandclust ering//AdvancesinNeuralInformat ionProcessingSystems. Vancouver ,Canada ,2002:585 591[17]Levy0, GoldbergY. Neuralwordembeddingasimplici tmatrixfactorizat ion// AdvancesinNeuralInformationProcessingSyst ems. Mont real , Canada,2014: 2177 2185[18]CaoS, LuW, XuQ. GraRep: Learninggraphrepresent ationswi thglobalst ructuralinformat ion//Proceedingsofthe24thACMInternationalonConferenceonInf ormat ionandKnowledgeManagement. Melbourne, Aust ralia, 2015: 891900 Mining. SanFrancisco , USA,2016: 855 864460 计 算机 学 报 2021年[19]OuM, CuiP, PeiJ ,etal. Asymmetri ctransitivitypreservinggraphembedding//Proceedingsofthe22ndACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.SanFrancisco,USA,201 6: 1105-1114[20]YangC,Li uZ,ZhaoD,etal. Networkrepresentationlearningwithrichtextinformation//Proceedingsofthe24 thInternationalJointConferenceonArtificialIntel ligence.BuenosAires,Argentina,2015:2111-2117[21]ZhuD,CuiP,ZhangZ,etal.I  Iigh-orderproximity preservedembeddingfordynamicnetworks. IEEETransactionsonKnowledgeandDataEngineering,2018 ,30(11): 2134-2144[22]EckartC,YoungG. Theapproximationofonematrixbyanotheroflowerrank. Psychometrika,1936,1(3 ) :211-2 18[23]LehoucqRB,SorensenDC,YangC. ARPACKusers?guide:Solutionoflarge-scaleeigenvalueproblemswithimplicitlyrestartedArnoldi methods.Philadelphia :SocietyforIndustrialandAppliedMathemati cs,1998[24]Tropp JA,YurtseverA,UdellM,et al.Practi calsketchingalgorithmsforlow-rankmatrixapproximation. SIAMJournalonMatrixAnalysisandApplications,2017 ,38 (4) : 1454-148 5[25]I lighamNJ. Matrixnearnessproblemsandappli cations//ProceedingsoftheIMAConferenceonAppli cations of MatrixTheory. NewYork,USA,1989: 1-27[26]BoydS,VandenbergheL. ConvexOptimization.Cambridge,UK:CambridgeUniversityPress,2004(Section4.2.3)[27]YuW, GuY,LiJ. Si ngle-passPCAoflargehigh?dimensionaldata//Proceedingsof the 26thInternationalJoi ntConferenceonArtificialIntelligence. Melbourne,Australia,2017 : 3350-3356[28]FengX, Xi eY,SongM,etal. FastrandomizedPCAforsparsedata//Proceedingsofthe10thAsianConferenceonMachineLearning.Beijing,China,2018 :710-725[29]StarkC,Brei tkreutzBJ , Chatr-AryamontriA,etal. TheBioGRIDinteractiondatabase: 201 1update. Nucl eicAcidsResearch,2010,39(Suppl_l):D698-D704[30]Social-DimensionApproachtoClassificationinLarge-ScaleNetworks, http: //leitang.net/social_dimension, html,2010.7. 29[3 1]Tang J , Zhang J, YaoL, etal.Arnetmi ner:Extractionandminingofacademicsocialnetworks//Proceedi ngsofthe14thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.LasVegas?USA,2008: 990-998[32]FanRE,ChangKW?I lsi ehCJ,etal. LIBLINEAR:Ali braryforlargeli nearcl assifi cation. JournalofMachineLearningResearch, 2008 ,9 :1871-1874[33]TangL,RajanS, NarayananVK. Largescalemulti-l abelclassificationviametalabeler//Proceedi ngsofthe18thInter?nationalConferenceonWorldWideWeb. Madrid,Spain,2009: 211-220[34]YangY. Anevaluationofstatisticalapproachestotextcategorization. InformationRetri eval,1999,1(1-2): 69-90[35]GodboleS,SarawagiS. Di scriminativemethodsformul ti-labeledcl assifi cation//Pacific-AsiaConferenceonKnowledgeDiscoveryandDataMining. Berl in, Germany:Springer,2004:22-30XIEYu-Yang,Ph.D.candidate.Hisresearchinterestsincludedataminingandmatrixanalysis.FENGXu, Ph.D.candidate.Hisresearchinterestismatrixanalysis.YUWen-Jian, Ph.D. ,associateprofessor.Hisresearchinterestsincl udecomputeraideddesignofICandmatrixanalysis.TANGJie, Ph.D. ,professor.Hisresearchinterestsincludesocialnetworkminingandacademicknowledgegraph.BackgroundInordertoprocessnetworkdataeffectively,thechallengeistofindeffectivenetworkdatarepresentation.Thetraditionalnetworkdatarepresentationhasbecomeabottleneckinlarge-scal enetworkdatanowadays.Networkembedding,whichaimstolearnlow-di mensionalvectorrepresentationsfornetworknodesandeffectivelypreservethenetworkstructure,i sapromisingwayofnetworkrepresentation.Duringthepastfewyears ,thereisasurgeofresearchonnetworkembeddi ng.DeepWalk, LINEandnode2vecmodel swhi chareskip-grambasedhavebeenconsideredaspowerfulbenchmarksolutionsfornetworkembeddingresearch.GraRep, HOPE, NetMF, NetSMFandProNEmodelsarematri xfactorizationbasednetworkembeddingmethods.NetMFalgorithmtheoreticallyunifiesseveral networkembeddingmethodsandshowtheembeddingl earnedbyNetMFisaspowerfulasthosel earnedfromtheskip-grambasedmethods.Themajordi sadvantageofexi stingmethodswhi chisbasedonmatrixfactori zati onisthelargecoston谢雨洋等: 基于随机化矩阵分解的网络嵌人方法 46 13 期computationandmemory.Inthiswork, weusefastrandomizedeigenval uedecomposition(EVD)andsinglepasssingularvaluedecomposition(SVD)toimproveNetMFandpresentanefficientrandomizedmatrixfactorizationbasednetworkembeddi ngalgorithm(eNetMF). Firstly, weproposeafastrandomizedEVDalgorithm(freigs)forsparsematri x. Secondl y, weproposetousesingl epassSVDapproachtoprocesshigh orderproximitymatrixintheNetMF, sothatwecanavoidstoringthelargedensematrixandlargelyreducethememorycost.Thirdl y, weproposeasi mplified, randomizedsinglepassSVDalgorithmthatguaranteesasymmetricdecompositionresult.Combiningtheabovetechniques,wefinallyobtaintheeNetMFalgorithm.Withfi verealnetworkdatasets, weevaluatetheeffici encyandeffectivenessoftheeNetMFalgorithmonmultil abelnodecl assification. ExperimentalresultsshowthatintermsofthemetricsMacro FIandMicro Fl , theembeddinggeneratedbyeNetMFhasthesameperformanceasNetMFinmul ti label nodecl assification.Benefitingfromrandomizedmatrixdecompositionalgorithms>eNetMFisfastandmemoryfriendlycomparedtoNetMF.Webelievetherandomizedmatrixdecompositionalgorithmsaregenericandcanbeappl iedtomatri xfactorizationbasednetworkembeddi ngmodels, andhopethi spaperwillinspiremorefutureresearchinthisarea.ThisworkissupportedbyNationalKeyR&DProgramofChina(GrantNo. 2020八八八0103502)andtheNationalNaturalSci enceFoundation( GrantNo. 61 87 2206). Thisworkfocusesontherandomizedmatrixdecompositionanditsapplicationinnetworkembedding. Ourgrouphasbeenstudyingrandomizedmatrixdecompositionandnetworkembeddingforyears, andhasproposedaseri esofworksuchasfrPC八, NetMF, NetSMFandProNE.

[返回]
上一篇:图像信息对句子语义理解与表示的有效性验证与分析
下一篇:基于目标导向行为和空间拓扑记忆的视觉导航方法_阮晓钢