【斯坦福大学公开课CS224W——图机器学习】一、图机器学习中的传统方法（1）

【斯坦福大学公开课CS224W——图机器学习】一、图机器学习中的传统方法（1）

1. 节点水平任务和特征

节点的任务主要是利用机器学习的方式实现对图数据的未知节点进行分类。

节点的特征——目标：表征网络中节点的结构和位置：节点的度、节点中心性、聚类参数、图元

1.1 节点的度

节点v的度kv是该节点有多少条边与之相连。

1.2 节点中心性（node centrality）

节点的度计算了相邻节点的个数，但没有捕获到他们的重要性。节点的中心性cv考虑了图中节点的重要性。

不同的方法来构建他们的重要性：特征向量中心性(Eigenvector centrality)、中间性中心性(Betweenness centrality)、紧密性中心性(Closeness centrality)和其他方法。

1.2.1 特征向量中心性（Eigenvector centrality）

将递归方程改写为矩阵形式。该方法可以简单理解为：自己的特征取决于邻近节点特征向量的标准化。

1.2.2 中间性中心性（Betweenness centrality）

该方法认为：如果一个节点位于其他节点之间的许多最短路径上，则该节点很重要。

1.2.3 紧密性中心性（Closeness centrality）

如果节点到所有其他节点的最短路径长度很小，则节点很重要。

1.3 聚类参数（Clustering coefficient）

1.4 图元（Graphlets）

通过观察发现，聚类系数计算自我中心网络（eco-network）中的三角形。我们可以通过计算预先指定的子图，即图元来推广以上内容。

目标：描述节点u周围的网络结构。

图元（Graphlets）是一个能够描述节点u的网络社区结构的小型子图。

类比来看，度计算了节点相接的边的个数；聚类参数计算节点周围边围成的三角形；图元度向量（Graphlet Degree Vector，GDV）：基于图元的节点特征。GDV计算节点触接的图元个数。

图元度向量提供了节点局部网络拓扑的度量。比较两个节点的向量提供了比节点度或聚类系数更详细的局部拓扑相似性度量。

诱导子图：诱导子图是另一个图，由顶点子集和连接该子集中顶点的所有边形成。

图同构：两个图包含相同数量的节点，以相同的方式连接，称为同构。

图元：有根连通诱导非同构子图。

• 我们有三种不同的轨道（orbit），轨道上有a、b、c、d四种节点位置（orbit position，图6中节点旁边标的数字）。对于节点v来说，其在轨道位置a上有2个图元，在轨道位置b上有1个图元，在轨道位置c上没有图元，在轨道位置d上有2个图元。这里需要注意的是图元是导出子图。

例如把V节点放在c的位置，而在原图中 这个图不是导出子图，故图元为0.

对于GDV的理解是：它提供了对于一个节点的本地网络拓扑的度量，这样可以比较两个节点的GDV来度量它们的相似度。由于Graphlet的数量随着节点的增加可以很快变得非常大，所以一般会选择2-5个节点的Graphlet来标识一个节点的GDV。

2. 总结

我们介绍了获得节点特征的不同的方法，他们可以按照以下标准进行分类：

基于重要性的特征：捕获图中节点的重要性；用于预测图中有影响的节点，例如预测社交网络中的名人用户

• 节点的度
• 不同的节点中心性方法

基于结构的特征：捕捉节点周围局部邻域的拓扑性质；用于预测节点在图中扮演的特定角色，例如蛋白质相互作用网络中蛋白质功能的预测

• 节点的度
• 聚类参数
• 图元计数向量（Graphlet count vector）