003传统图机器学习、图特征工程

---

一. 人工特征工程、连接特征

• 节点、连接、子图、全图都有各自的属性特征， 属性特征一般是多模态的。
• 除属性特征外，还有连接特征。本讲侧重点为：用人工特征提取的方法对连接特征进行提取。

二. 在节点层面对连接特征进行特征提取

• 节点的度：只看连接个数，不看连接质量。
• 节点的中心性：

1. 特征向量中心性：其原理是某节点周围的节点都很重要，那么它也重要。
2. 中介中心性：其原理是若某节点处于交通咽喉，那么它很重要。
3. 邻接中心性：其原理是若一个节点去哪都近，那么它很重要。

• 节点的聚集系数：衡量节点周围的抱团程度，其实就是查以该节点为端点的三角形个数。
• Graphlets：聚集系数中的三角形结构可以视为一种子图，那么用其他子图代替三角形结构也是可以的，这就是Graphlets。提取某节点周围不同子图的个数，就可以构成一个向量Graphlet Degree Vector（GDV）。这个向量就可以用于描述节点的邻域拓扑结构信息。
• 还有其他的衡量方式如：PageRank、Katz中心性等。在NetworkX里包含多种数据挖掘算法可供使用。

三. 在连接层面对连接特征进行特征提取

• 即提取连接的特征，把连接变成 d 维向量。
• 基于两节点的距离：

• 两节点间最短路径长度：只看长度，忽略个数、质量。

• 基于两节点局部连接信息：

1. 两节点共同相邻节点个数（交集）
2. 两节点相邻节点的交并集合个数比
3. Adamic-Adar index：

• $S_a={\sum }_{u\in N(V_1)\cap N(V_2)}\frac{1}{log(k_u)}$。
• 可以这样理解，两个人的连接若通过几个公众人物，那么他俩大概率不会很亲近。若通过一个普通人，那大概关系是不错的。

存在一个问题，如果两个节点没有共同的邻域节点，则以上三个指标都为 0 没有意义，这就需要看全图的信息了。

• 基于两节点在全图的连接信息——Katz index：

• 记录两节点间长度为k的路径个数。
• 其可以通过邻接矩阵的幂来求解。
• 设图的邻接矩阵为A，则节点u、v之间长度为k的路径个数是$A^k$矩阵的第u行第v列的值。
• 公式为$S_{u,v}={\sum }_{l=1}^{\infty }{\beta }^l{A}_{u,v}^l=（I-\beta A{）}^{-1}-I$，其中$\beta$是缩放因子，得到的是katz系数矩阵。

四. 在全图层面对连接特征进行特征提取

• 所得的特征应该能反映全图的结构特点。
• Bag-of-node-degrees：只看节点的度，不看连接结构 。实际上还是数数，数不同度对应的节点个数。
• Graphlet Kernel：

• 数 Graphlet 的个数得到 Bag-of-Graphlet，算是 Bag-of-* 的推广。
• 与节点层面不同从全图的角度 Graphlet 可以有孤立节点。
• 统计各种 Graphlet 的个数，也可以构成 d 维向量。
• 对两个图的 Bag-of-Graphlet 做归一化后，再做数量积就得到它俩的 Graphlet Kernel。
• 然而 Graphlet Kernel 计算复杂度过高，应用空间很小，引出Weisfeiler-Lehman Kernel。

• Weisfeiler-Lehman Kernel：

• 其特点是通过迭代不断丰富节点词库。
• 其用到的是颜色微调的方法。
• 通过多次迭代，进行节点颜色微调，丰富节点词库，最后统计不同颜色节点出现的次数，得到向量，实现特征提取。
• 对两个图的向量进行数量积运算，所得即 Weisfeiler-Lehman Kernel 。
• 一般迭代次数越多，效果越好。
• 注1：计算两个图的 Weisfeiler-Lehman Kernel 时，迭代计算要同时进行，即节点颜色词库要由两个图同时贡献。
• 注2：NetwokX 里的 weisfeiler_lehman_graph_hash 实现与上面说的不一样，gklearn.kernels.Weisfeilerlehmankernel 才是一样的。