人力招聘网站建设目的,腾讯云服务器备案,网站建设就业前景2017,wordpress添加快速添加按钮前言
随着图谱应用的普及#xff0c;图深度学习技术也逐渐被越来越多的数据挖掘团队所青睐。传统机器学习主要是对独立同分布个体的统计学习#xff0c;而图深度学习则是在此基础上扩展到了非欧式空间的图数据之上#xff0c;通过借鉴NLP和CV方向的模型思想#xff0c;衍生…前言
随着图谱应用的普及图深度学习技术也逐渐被越来越多的数据挖掘团队所青睐。传统机器学习主要是对独立同分布个体的统计学习而图深度学习则是在此基础上扩展到了非欧式空间的图数据之上通过借鉴NLP和CV方向的模型思想衍生了很多对图谱这种非序列化数据的建模分析手段帮助分析人员洞察数据之间隐含的复杂关系特征。
在深度学习技术没有普及之前已经存在大量的图谱数据分析工作而这些工作的主要思路是通过抽取图中节点的统计信息作为特征并用作分类模型的输入。今天在这里介绍的其中一个经典的图分析算法叫做特征向量中心度eigenvector centrality它的作用是衡量节点在整个网络中的重要性。图数据一个最常用的数据结构就是邻接矩阵而这个算法的主要思想就是用到了矩阵分解的思想经典的图深度学习算法GCN也是基于拉普拉斯矩阵的谱分解和傅立叶变换实现的。所以对于新人来说特征向量中心度可以做为图数据挖掘的经典入门算法之一。
参考资料
[1] William L. Hamilton. Graph Representation Learning. Morgan and Claypool publishers, 2020
[2] Xinyu Chen. 幂迭代法[OL]. https://zhuanlan.zhihu.com/p/336250805
[3] Power method for approximating eigenvalues, https://ergodic.ugr.es/cphys/lecciones/fortran/power_method.pdf
[4] 柴静. 线性代数-山东大学. https://www.bilibili.com/video/av370427050/?p42vd_source9ca707c71dee64c77d2f5f3d824e1c19定义问题
图片引用自 《交网络舆情中意见领袖主题图谱构建及关系路径研究_基于网络谣言话题的分析》
我们首先来定义特征向量中心度算法所要解决的问题。如上图所示这是微博谣言话题中意见领袖节点关系图谱的一部分。如果用最简单直观的图统计方法来分析这个图谱那就是使用节点的出入度的大小有多少邻节点来衡量这个节点在图谱中的重要性。我们可以看到”天涯历知幸“、“来去之间”和“开水族馆的XX”三位博主的出入度最高是重要的意见领袖。但是如果仅仅是通过博主周围的邻居节点的数量来衡量其影响力又是有失偏颇的因为这些转发和关注的微博用户有可能是僵尸粉现在僵尸粉都很智能的。所以我们还需要找到一种方式不仅仅是通过当前节点关联的邻居节点数量来横量其重要性还要将邻居节点本身的重要性也一起考虑进去。回到上图“鸟窝里的猫妖”和“筆木鱼_”这两个节点虽然它的邻居节点数量很少但是它们都关注转发了”天涯历知幸“、“来去之间”和“开水族馆的XX”三位重要博主的博文所以他们也应该是重要的谣言传播者。
算法原理
我们先定义eue_{u}eu 节点的特征向量中心度由下面的递归等式表示
eu1λ∑v∈νA[u,v]ev∀u∈νe_{u} {\frac{1}{\lambda}\sum_{v\in \nu} } A[u,v] e_{v}\;\; \forall u \in \nueuλ1∑v∈νA[u,v]ev∀u∈ν, (1),
这个等式的意思是eue_{u}eu 节点的中心度是其周围邻节点eve_{v}ev 中心度总和的1λ\frac{1}{\lambda}λ1, 其中λ\lambdaλ是一个常量。ν\nuν是图上所有节点的集合。AAA是邻接矩阵A∈R∣ν∣×∣ν∣A \in \mathbb{R}^{|\nu| \times |\nu|}A∈R∣ν∣×∣ν∣, A[u,v]1A[u,v] 1A[u,v]1 代表节点uuu和节点vvv之间相连节点之间存在边关系A[u,v]0A[u,v] 0A[u,v]0 代表节点uuu和节点vvv之间不相连。 从上面的式子来看如果在一个很大的图谱上做递归运算且图谱的度数很深甚至存在环路则需要非常大的栈内存同时计算效率也不高。
那么我们再对公式进行转换假设eee是图谱上所有节点中心度的集合也就是
e{e1,e2,e3,……,ev}Te \big\{e_{1},e_{2},e_{3},……, e_{v} \big\}^{T}e{e1,e2,e3,……,ev}T (2),
那么将式子(2) 代入式子 (1), 得我们可以得到下面的式子(3)
λeAe{\lambda}e AeλeAe (3),
我们可以发现式子(3)就是一个典型的特征值方程其中eee是邻接矩阵AAA的特征向量λ{\lambda}λ是邻接矩阵的特征值。 定义设A是n阶矩阵λ{\lambda}λ为一个数若存在非零向量X使得λXAX{\lambda}X AXλXAX, 则称数λ{\lambda}λ为矩阵A的特征值非零向量X为矩阵A的对应于特征值λ{\lambda}λ的特征向量。 则我们可以将图谱领接矩阵A的特征向量eee做为其每个节点的中心度度量值。同时我们也希望衡量节点中心度的值为正数那么通过Perron-Frobenius定理我们可以证明特征向量eee中的每一个分量都是正值满足节点中心度的度量值的要求。 Perron–Frobenius定理证明了存在一个方阵如果其行列的元素为正值则存在最大的特征值λpf{\lambda}_{pf}λpf并且该特征值所对应的特征向量的每个元素都是正数。 由上面的公式和定理可以得知一个矩阵如果存在最大的特征值那么这个特征值就是该矩阵的主特征值其对应的特征向量则是主特征向量并且主特征向量里面的每一个元素都是正数。我们可以将邻接矩阵A的主特征向量eee的每一个分量值作为其节点所对应的中心度度量值它体现了节点所连接的邻节点的数量以及所连接邻节点的重要性。
那么我们来看看特征向量的一般求法以公式(3)为例A是n阶邻接矩阵移项后公式(3)可以写成 (A−λE)e0(A-{\lambda}E)e0(A−λE)e0 (4), 其中EEE是n阶单位矩阵。又因为eee是非零向量那么可以进一步得出 A−λE0A-{\lambda}E0A−λE0 (5), 解此行列式即公式(5)获得的值λi\lambda_iλi即为矩阵A的特征值 再将λi\lambda_iλi值代入公式(4)中就可以求出对应的特征向量。
例如A∣1−22−2−2424−2∣A \begin{vmatrix}1-22\\-2-24\\24-2\end{vmatrix}A1−22−2−2424−2 那么 A−λE∣1−λ−22−2−2−λ424−2−λ∣0A-{\lambda}E \begin{vmatrix}1-\lambda-22\\-2-2-\lambda4\\24-2-\lambda\end{vmatrix}0A−λE1−λ−22−2−2−λ424−2−λ0 (1−λ)(2λ)2−16−164(2λ)−16(1−λ)4(2λ)0(1-\lambda)(2\lambda)^2-16-164(2\lambda)-16(1-\lambda)4(2\lambda)0(1−λ)(2λ)2−16−164(2λ)−16(1−λ)4(2λ)0 −λ3−3λ224λ−280-\lambda^3-3\lambda^224\lambda-280−λ3−3λ224λ−280 我们看见一个3阶矩阵的行列式方程就有3个根λ1,λ2,λ3\lambda_1,\lambda_2,\lambda_3λ1,λ2,λ3。那么如果图谱是100万的节点那么就会组成一个100万阶的邻接矩阵它的行列式方程将有100万个根。由此可见我们需要找到一个更加合理的办法去求出大图的特征向量。
这时候我们要引入幂迭代 (power iteration) 法。 幂迭代 (power iteration) 法是线性代数中一种非常重要的方法可对特征值分解和奇异值分解等问题进行求解。比较特别的是当我们要对来自真实世界的大规模数据进行奇异值分解时基于幂迭代法的奇异值分解在保证精度的同时可以极大提高计算效率。[2] 类似于Jacobi和Gauss-Seidel两个迭代算法幂迭代 (power iteration) 法也是采取迭代计算的方式去得到一个近似值逼近主特征向量。假设我们有一个具有主特征值的邻接矩阵AAA我们选取一个非零向量x0x_0x0作为矩阵AAA的主特征向量的初始向量那么幂迭代的计算方法如下 x1Ax0x_1 Ax_0x1Ax0 x2Ax1A(Ax0)A2x0x_2 Ax_1A(Ax_0)A^2x_0x2Ax1A(Ax0)A2x0 x3Ax2A(A2x0)A3x0x_3 Ax_2A(A^2x_0)A^3x_0x3Ax2A(A2x0)A3x0 ………… xkAxk−1A(Ak−1x0)Akx0x_k Ax_{k-1}A(A^{k-1}x_0)A^kx_0xkAxk−1A(Ak−1x0)Akx0 当k足够大的时候也就是迭代次数足够多时我们就能逼近矩阵AAA的主特征向量。
例如有一个矩阵A[2−121−5]A \begin{bmatrix}2-12\\1-5\end{bmatrix}A[21−12−5]且假设一个初始化的非零特征向量为x0[11]x_0 \begin{bmatrix}1\\1\end{bmatrix}x0[11] 使用幂迭代法我们可以得到以下计算过程
x1Ax0[2−121−5][11][−10−4]−4[2.501.00]x_1Ax_0 \begin{bmatrix}2-12\\1-5\end{bmatrix} \begin{bmatrix}1\\1\end{bmatrix}\begin{bmatrix}-10\\-4\end{bmatrix}-4\begin{bmatrix}2.50\\1.00\end{bmatrix}x1Ax0[21−12−5][11][−10−4]−4[2.501.00] x2Ax1[2−121−5][−10−4][2810]10[2.801.00]x_2Ax_1 \begin{bmatrix}2-12\\1-5\end{bmatrix} \begin{bmatrix}-10\\-4\end{bmatrix}\begin{bmatrix}28\\10\end{bmatrix}10\begin{bmatrix}2.80\\1.00\end{bmatrix}x2Ax1[21−12−5][−10−4][2810]10[2.801.00] x3Ax2[2−121−5][2810][−64−22]−22[2.911.00]x_3Ax_2 \begin{bmatrix}2-12\\1-5\end{bmatrix} \begin{bmatrix}28\\10\end{bmatrix}\begin{bmatrix}-64\\-22\end{bmatrix}-22\begin{bmatrix}2.91\\1.00\end{bmatrix}x3Ax2[21−12−5][2810][−64−22]−22[2.911.00] ………… x6Ax5[2−121−5][−280−94][568190]190[2.991.00]x_6Ax_5 \begin{bmatrix}2-12\\1-5\end{bmatrix} \begin{bmatrix}-280\\-94\end{bmatrix}\begin{bmatrix}568\\190\end{bmatrix}190\begin{bmatrix}2.99\\1.00\end{bmatrix}x6Ax5[21−12−5][−280−94][568190]190[2.991.00]
经过第6次的迭代我们发现向量x6x_6x6的单位向量[2.991.00]\begin{bmatrix}2.99\\1.00\end{bmatrix}[2.991.00]已经十分接近矩阵AAA真实的主特征向量[31]\begin{bmatrix}3\\1\end{bmatrix}[31].
当然随着迭代次数的增大矩阵计算中的各分量元素在计算过程中可能会出现数值溢出所以我们需要对每个元素进行归一化处理幂迭代法的一般性算法可以写为 step1: xkAxk−1x_k Ax_{k-1}xkAxk−1 step2: xkxk/∥xk∥2x_k x_k/\|x_k\|_2xkxk/∥xk∥2 其中∥xk∥2\|x_k\|_2∥xk∥2是特征向量的ℓ2\ell_2ℓ2范数意思是特征向量中所有元素的平方和再开方。 有一种观点认为特征向量中心度是在图中进行无限长度的随机游走时一个节点被访问到的可能性的排序从上述的幂迭代法就可以看出这个观点依据。[1] 以上就是特征向量中心度算法的基本实现原理。大家有时间也可以学习一下Rayleigh quotient表达式它是在知道矩阵特征向量的前提下计算矩阵对应特征值近似解的方法。
源码解析
接下来我们将从一个开源框架SparklingGraph去学习如何用代码实现中心度的计算。因为我们平时在处理工业界的图数据时都是上亿的节点和边所以这也是为什么去选择一个分布式的图计算框架来讲解。 GitHub : https://github.com/sparkling-graph/sparkling-graph 因为该开源框架是基于Spark Graphx去实现的图计算方法所以其开发语言是100%的Scala。这里建议大家具备一些Spark和Scala的基础知识不然下面的源码解读比较难以理解。 Spark Graphx的官网 https://spark.apache.org/docs/latest/graphx-programming-guide.html 我们直接解读核心单例对象EigenvectorCentrality中的computeEigenvector方法
/*** Created by Roman Bartusiak (roman.bartusiakpwr.edu.pl http://riomus.github.io).*/
object EigenvectorCentrality extends VertexMeasure[Double]{/*** Generic Eigenvector Centrality computation method, should be used for extensions, computations are done until continuePredicate gives true* param graph - computation graph* param vertexMeasureConfiguration - configuration of computation* param continuePredicate - convergence predicate* param num - numeric for ED* tparam VD - vertex data type* tparam ED - edge data type* return graph where each vertex is associated with its eigenvector*/
1 def computeEigenvector[VD:ClassTag,ED:ClassTag](graph:Graph[VD,ED],vertexMeasureConfiguration: VertexMeasureConfiguration[VD,ED],continuePredicate:ContinuePredicateconvergenceAndIterationPredicate(1e-6))(implicit num:Numeric[ED]){
2 val numberOfNodesgraph.numVertices
3 val startingValue1.0/numberOfNodes
4 var computationGraphgraph.mapVertices((_,_)startingValue)
5 var iteration0
6 var oldValue0d
7 var newValue0d8 while(continuePredicate(iteration,oldValue,newValue)||iteration0){
9 val iterationRDDcomputationGraph.aggregateMessages[Double](
10 sendMsg context{
11 context.sendToDst(num.toDouble(context.attr)*context.srcAttr)
12 context.sendToSrc(0d)
13 if(vertexMeasureConfiguration.treatAsUndirected){
14 context.sendToSrc(num.toDouble(context.attr)*context.dstAttr)
15 context.sendToDst(0d)
16 }
17 },
18 mergeMsg (a,b)ab)
19 val normalizationValueMath.sqrt(iterationRDD.map{case (_,e)Math.pow(e,2)}.sum())
20 computationGraphcomputationGraph.outerJoinVertices(iterationRDD)((_,_,newValue)if(normalizationValue0) 0 else newValue.getOrElse(0d)/normalizationValue)
21 oldValuenewValue
22 newValuecomputationGraph.vertices.map{case (_,e)e}.sum()/numberOfNodes
23 iterationRDD.unpersist()
24 iteration1
25 }
26 val outcomputationGraph
27 out.unpersist(false)
28 out
29 }需要注意的是第1行代码中computeEigenvector方法中有一个隐式变量(implicit num:Numeric[ED])这里其实是指GraphX对象中边上的属性是要可计算的这里相当于是边的权重值。 这个方法的输入主要是GraphX对象它是由VertexRDD和EdgeRDD组成由用户自己从数据源读取图数据生成。另外输入的就是封装了算法参数的VertexMeasureConfiguration对象。
第2-3行表示计算全图的节点所有节点的初始值为1.0/总节点数。这里相当于幂迭代法中初始化的主特征向量值。 第4行表示用一个map方法将节点的属性都统一成我们之前的初始化值且节点只包含这一个属性值并以此形成后续迭代所用的计算图。 第8行到第24行就是我们之前说的幂迭代法的循环体它的循环控制是由convergenceAndIterationPredicate这个函数实现的。
/*** Created by Roman Bartusiak (roman.bartusiakpwr.edu.pl http://riomus.github.io).*/
object EigenvectorUtils {type ContinuePredicate(Long,Double,Double)Booleandef convergenceAndIterationPredicate(delta:Double, maxIter:Long100)(iteration:Long, oldValue:Double, newValue:Double){Math.abs(newValue-oldValue)delta iterationmaxIter}
}这个函数是用来控制循环体什么时候停止当迭代循环的次数大于100时或者前一次迭代计算的值和当前迭代计算的值的差的绝对值小于一个极小值那么循环就停止。从上面的代码可以看出这个极小值默认为1e-6.
第9-18行则是使用Graphx的消息发送算子aggregateMessages定义了图上每个节点向邻居节点所发送的消息以及节点收到消息后的合并方法。我们从上面可以看到第11行就代表着将每一条边上的开始(source vertex)节点的值乘以当前边的权重然后发送到结束节点target vertex。每个节点的初始值就是我们在第2-3行代码里定义的初始化的值。第18行就是节点对消息的聚合函数这里看到就是全部相加。 这段代码本质就是将当前节点的所有邻居节点的中心度值发送过来并进行聚合相加当做当前节点的中心度值。让我们回顾一下邻接矩阵A[u,v]1A[u,v] 1A[u,v]1 代表节点uuu和节点vvv之间相连为0则不相连所以这个聚合相加操作本质上就等于我们幂迭代法中邻接矩阵和主特征向量的矩阵相乘。这就是整个代码的核心比较抽象大家可以多花些时间思考和理解。
第19-20行实际上就是主特征向量的ℓ2\ell_2ℓ2范数计算也就是归一化。
最终输出的也是一个Graphx对象其中的VertexRDD由一个二元组节点ID节点的特征向量中心度组成。
以上就是特征向量中心度的算法原理与源码解析希望对大家有帮助。文章中有写得不正确的地方希望大家帮忙指出并给我留言谢谢各位读者。
