CS224W(1.14)Lecture 2. Traditional Methods for ML on Graphs-针对节点的特征工程方法

前言

这节课主要介绍传统的图机器学习方法。传统方法主要分为两步,第一步人工设计特征,第二步使用各种机器学习方法进行预测。因此,特征工程在传统图机器学习方法中有很重要的地位。本节课主要介绍图上的特征工程方法,分别介绍针对节点(node-level)、边(link-level)和图(graph-level)的特征工程方法。

针对节点的特征工程方法

节点水平的特征主要有四类,下面分别介绍。

  • 节点的度(node degree)
  • 节点的中心性(node centrality)
  • 节点的集聚系数(clustering coefficient)
  • 非同构子图(graphlets)

节点的度

节点的度,这个最好理解了,即该节点的所连边的数目,或者说该节点的直接邻居数目。如果是有向图,还分为出度和入度。

节点的度的不足是,没有考虑到不同邻居的重要性不同,只要有一个邻居,度就加1,即认为所有邻居的重要性是相同的。

节点的中心性

节点的中心性这个特征考虑了节点的重要性,有多个中心性指标,如下:

  • 特征向量中心性(Engienvector centrality)
  • 中介中心性(Betweenness centrality)
  • 接近中心性(Closeness centrality)

特征向量中心性的定义是:节点v的重要性=v的邻居的重要性的和,除以λ进行归一化。

根据定义可知,特征向量中心性是递归定义的,写成矩阵形式就是Ac=λc,特征向量c的每个维度就是每个顶点的特征向量中心性的值。

忘记了怎么求特征值和特征向量的同学可以复习一下:https://blog.csdn.net/Junerror/article/details/80222540

算出最大特征值λ_max对应的特征向量c_max之后,节点v的特征向量中心性就是向量c_max的第v个分量。具体看维基百科:https://zh.wikipedia.org/zh-cn/%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F%E4%B8%AD%E5%BF%83%E6%80%A7

如果说特征向量中心性有点难以理解和计算的话,接下来介绍的中介中心性和接近中心性就很好理解了。

中介中心性,顾名思义,就是节点作为中介(枢纽)的重要性。计算方法是,所有节点对(s,t)的最短路径穿过节点v的比例。(s,t)的最短路径可以认为是(s,t)之间的交通要道,如果这条路径穿过节点v的话,说明v在交通要道上,所以v是很重要的中介枢纽。具体计算方法见下图,即v在所有(s,t)的最短路径中出现的比例。

接近中心性也很好理解,就是节点v与图中其他节点的接近程度。计算方法是:v到其他节点的最短路径之和的倒数。如果一个节点越中心,则它到其他节点的最短路径越短,则接近中心性越大。比如下图的D就比A更中心,所以D的接近中心性更大。

节点的集聚系数

集聚系数是个很有意思的指标,它描述的不是节点本身,而是节点的邻居的集聚程度。其计算公式如下图所示,分子是v的邻居形成的边的数目,分母是v的邻居理论上能形成最多的边的数目,分母用来归一化的。

集聚系数=1表示v的邻居都两两认识,=0表示v的邻居两两都不认识。集聚系数越大,表示邻居聚集程度越高,越有可能是一个紧密的团体。

非同构子图

非同构子图的英文定义是:rooted connected non-isomorphic subgraphs,很准确啊,有根的连通的非同构子图。比如下图中3个节点的graphlets有3个,G1中目标节点(根节点)在1和2形成的子图是不一样的(不同构),而在G2中3个点的位置是等价的,所以G2只有1个graphlet,加起来就是3个graphelts。从2个节点到5个节点,能形成的graphlets总数是73个。

Graphlet Degree Vector(GDV)是基于graphlets的特征,它计算以目标节点v为根,能形成的不同graphlets的数目向量,相当于描述了v周围不同子结构的子图个数。如下子图3所示,红色节点v的2-3个节点的GDV向量是[2,1,0,2]。如果统计节点v周围的2~5个节点(包含v自己)形成的graphlets的数目,则会得到一个维度为73的GDV向量,相当于节点v的一个特征向量。这个73维度的特征向量是节点v周围四跳(4-hop)的结构信息。

小结一下节点的特征大概可以分成两类,一类是基于重要性的特征,例如节点的度、节点的中心性;另一类是基于结构的特征,例如节点的度、集聚系数、非同构子图个数向量。基于重要性的特征可用于预测网络中的重要节点,例如社交网络中的名人节点;基于结构的特征可用于预测网络中不同节点的不同功能,例如蛋白质相互作用网络中不同蛋白质的功能,因为不同的局部子结构往往蕴含了不同的功能。

Leave a Reply

Your email address will not be published. Required fields are marked *