传统图机器学习的特征工程【斯坦福CS224W】

Cold

机器学习的任务

我们不可能直接把整个图输入给计算机，计算机只能看得懂向量、矩阵这样的结构化数据，因此传统的方法就是人工设计特征，把节点的特征、连接特征、图的特征用 d 维向量的方式输入，用于后续的机器学习。

特征有属性信息和连接信息

特征工程

好的特征是取得更好的模型效果的前提

节点层面

由已知的节点的信息去猜未知节点的节点分类问题，属于是半监督的节点分类问题

可以通过节点的度数，节点的重要度，节点的聚集系数（比如说B，C，D之间的抱团情况），自己定义子图的模式看图中的情况（Graphlets）

Node Degree

从Node Degree的角度来看，可能A节点（院士C的关门弟子）和G（杰青E的博士）的特征是一样的，但是从重要程度上来看，肯定是A > G的，因此我们还要考虑节点的重要程度

将邻接矩阵和全一的列向量相乘，就可以得到节点的重要程度（统计该节点的度数），这个数据就可以成为特征的一个维度

Node Centrality

Eigen vector centrality

一个节点的重要程度，由其相连的节点的重要程度决定

我们先来回顾一下特征向量的相关知识，对于上述的左侧的公式， C_v = \frac{1}{\lambda}\Sigma C_{u} 将 \lambda 移到左侧，可以得到 \lambda c = \Sigma C_{u} ,对于 \Sigma C_{u} ,用矩阵乘法的方式表示就是，相邻节点乘以对应节点的中心程度的向量。ex. 第一行的数据就是节点 0 和所有结点的连接情况（有连接为1，无连接为0），按照矩阵的方式相乘，和其有相连关系的节点乘以其对应的中心程度，其和左侧的公式含义是等价的

因此对于 \lambda c = Ac ，A 是图的邻接矩阵的表示，C 是表示对应节点的重要程度的列向量，也是邻接矩阵 A 的属于特征值 \lambda 的一个特征向量， \lambda 就是对于邻接矩阵 A 的一个特征值

因此可以利用如下的性质，求出特征值 \lambda

Betweeness centrality

衡量一个节点是否处于交通咽喉，必经之地

以 C 节点为例，公式的分母为除了该节点外，两两节点的对数，此处就是除了 C 之外，还有 4 个节点 C_{4}^{2}=6 ,公式的分子为：两两节点的对数中，有多少对节点的最短路径必须经过某节点的，此处就是 A-C-B，A-C-D，A-C-E，总共有三对节点，因此 Betweeness centrality 为 3 / 6 = 0.5；

Closeness centrality

衡量一个节点到其他节点距离的远近

Clustering Cofficient

衡量节点的集群系数（有多抱团）

分母：相邻节点两两对数（ C_{n}^{2} ）

分子：相邻节点两两联通的对数（把 v 节点断开以后）（可以直接通过数三角形来看）

Clustering Cofficient

描述节点局部邻域中的拓扑信息

Summary

连接层面

Link-Level的预测

如果他们的共同好友是一个海王，那么A-B之间的连接就会显得比较弱（因为认识的是公众人物），如果共同好友是一个深居简出的人，那么A-B的连接肯定会相对比较深。

这样只计算共同好友的方式，有一定的局限性，因为在实际生活中他们常常都是0，但在未来他们仍然有很大的潜力连接在一起，因此要引入全局的信息来解决这个问题。

卡兹系数：计数，节点之间长度为 k 的路径的个数（用邻接矩阵来实现）

由于长度太大的话，并没有什么意义，因此选择一个折减系数，乘在前面。

Summary

Graph层面的特征

我们的目标是为graph设计一组特征向量来表示，因此引入nlp中的Bag-of-words的策略，把图看作文章，把节点看作单词，倘若该节点出现过就记录为 1 否则为 0。对于下图中的两种图结构，两种不同的结构但却有着相同的特征向量表示，因此这样的特征向量表示方法是不够完善的。

因此我们设想，是否可以将图表示为Bag of node degrees？通过这样的方式，对于刚才的例子，我们似乎是已经解决了这个问题，但是对于更加复杂的图来说呢。

总的来讲，我们可以利用Bag-of-的思想，用更加精细的特征来表示一张图

通过上图 graphlets of size k 的定义，我们可以将其作为特征来表示图。这样的图的表示和之前节点层面的特征工程有所不同，不同点在于，现在是全图的视角来看，可以存在孤立节点，计数全图的Graphlet个数，而非特定节点邻域中Graphlet个数

全图上做匹配

代码实现

Graphlet Kernel

将两张图的 Graphlet Count Vector 做数量积，就可以得到 Graphlet Kernel（反映出两张图的相似程度）有的时候两个图规模不一致可能会导致图核值偏斜程度严重，因此在计算图元核之前可以先对图元统计向量进行归一化操作（如下图所示）

当然这样子的方法缺点也非常的明显

对于size = n 的图，数 size = k 的子图的时间复杂度是 n^{k}

另外不可避免的是子图同构测试（判断一个图是否是另一个图的子图）这是一个 NP-hard问题

若节点的度数被限制到了 d ，复杂度为 O(nd^{k - 1}) 仍然非常高

Weisfeiler-Lehman Kernel

能否用设计出一种更加高效的核方法呢？因此我们设计出了 Weisfeiler-Lehman Kernel 来解决这个问题

Weisfeiler-Lehman核方法的思想是：使用邻域结构来迭代扩张节点的词汇信息。为实现这个目标，核方法采用了一个名为 “Color Refinement” 的算法以迭代的方式生成图的向量表示：给定一个图 G 以及对应的节点集合 V ，首先我们为每个节点 v 指定一个初始的颜色 c^{0}\left( v \right) ；接着我们根据如下公式迭代地对节点颜色进行细化：