【CS224W】 -- 传统图机器学习的特征工程_cs 224w

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

一个图数据的层面包括：

• 节点层面
• 连接层面
• 全图层面

图机器学习需要的输入是一张图（矩阵），但是传统机器学习的输入向量没有图（矩阵）的形式，所以我们需要将不同层面的信息向量输入，相当于叠加成矩阵

节点和边的特征

节点、连接、子图、全图都可以有特征，其中特征可能是多模态的（图像、视频、文本、音频）

• 属性特征：某个节点自己就具有的特征
• 连接特征：一个节点在图中和其他节点的连接关系

传统图机器学习关注的特征

在传统的图机器学习中主要关注的是连接特征，而不是属性特征，更关注图中某个节点是桥接、枢纽还是边缘节点，侧重于研究这个 节点在他的社群中扮演什么角色

特征工程

假设我们现在有一个数据集是某一种花的四个特征，我们通过训练得到了一个机器学习模型，当一个新的花的图片到来的时候我们就可以放到模型中，去观察新的图片在这四个特征上的占比分别是多少，最终来判断这是什么花

而特征工程所要做的事情就是：设计一些其他特征，这些自己设置的特征相比于之前的特征能够更好地去分辨花的种类，通过人工的方式去将一些我们认为可能比较重要的特征用向量表示出来给模型

1. 节点层面的特征工程

以无向图为例，如何将节点、边、全图的特征用向量表示就是图中的特征工程

以节点分类为例：

半监督节点分类问题，由已知信息推出未知的信息

• 根据左图的已知节点（绿色、红色）推测出灰色的未知节点

图机器学习在节点层面的主要任务是对节点进行分类和学习图的结构特征，主要有：

• 节点的连接数（度）
• 节点的重要度
• 节点的聚集系数（和相邻节点是否有边相连）
• 自己定义一些子图的模型（数出节点周围有多少个我们构造的子图

1.1 节点的度

节点 $v$ 的度数 $k_v$ 为节点所拥有的边（相邻节点）。 但是节点度的这个特征不做区分地对待每个相邻的节点，因此在某种意义上，就没法对相同节点度的节点进行区分，即使它们可能位于网络中的不同部分。

如上图所示，如果只看节点连接数，那么下图中A,G节点的特征是相同的，但是两个节点所处的圈子的质量是完全不同的

（无向图中）获取节点的连接数，既可以通过数邻接矩阵中对应节点的一行或者一列，也可以使用如下图所示的方式乘以一个全为1的列向量（相当于每一行求和），计算出每一个节点的连接数。

度中心性：**最终得到的这个每个节点的连接数的值就可以作为D维向量的第一维。**比如节点3的度计算出来就是3，第一维就是3。

由于节点往往还要考虑节点的质量，所以我们除了考虑节点连接数还要考虑节点的重要度

1.2 节点重要度

对于节点重要度，有以下方法：

(1)Eigenvector centrality（特征向量重要度）

• 如果一个节点和他相连的节点非常重要，那么这个节点也非常重要
• 即，某一个节点的重要度等于与他相连的邻居节点的重要度求和再除以常数λ（归一化）
• 本质就是一个递归问题，需要迭代的求解

如上图所示求和将λ乘到左边，就可以等价为求矩阵A的特征向量的问题，上图的公式可以做如下解释：

• 如果图中一共有四个节点，那么c向量就是一个4行一列的向量，每一行都是一个节点的特征向量重要度
• 等号右边等价于一个矩阵✖c向量
• 矩阵A每一行对应的就是和当前节点相连的边的数量，和c相乘就是左边的每一个节点的特征重要度求和的意思
• 此时c向量就是矩阵A的特征向量，λ就是矩阵A的特征值
• 最终求解出来的特征向量的每一个值就是对应节点的特征向量重要度

(2)Betweenness centrality（中介中心性）

• 中介中心性用于刻画一个节点是否处于交通咽喉（必经之地）
• 计算案例如下图所示：

• 如上图算C节点的中介中心性
  • 除了C节点之外其他四个节点的两两组合就会有C42=6
  • 计算这六对的最短距离，有哪些一定要经过C
  • 最终带入公式就能计算出节点的中介中心性

(3)Closeness centrality（连接中心性）

• 连接中心性刻画了一个节点是否去哪儿都近
• 计算案例如下图所示：

• 某一个节点的连接中心性越高说明这个节点越在图中的中心位置

1.3 节点聚集系数（数三角形的个数）

Clustering Coefficient聚集系数就是节点有多抱团（和相邻节点是否有边相连），简单来说就是看图中的三角形个数

计算案例如下图所示：

其中有一种自我中心网络ego-network就是数三角形的个数，而这种三角形其实就是我们人为定义的一种子图，当然我们也可以定义其他形状来作为子图，也就是Gtaphlets

1.4 构造子图（数子图个数）

Gtaphlets构造子图就是如下图所示：

• 两个节点能构成一种子图，有一种节点角色
• 三个节点能构成两种子图，有三种节点角色
• 四个节点能构成六种子图
• 五个节点能构成的子图中，有0-72共73个节点角色

什么是节点角色呢？节点角色的定义是在网络中具有相似位置的点的集合，类似于化学中的同分异构体，进一步说这个定义和 community 其实是互补的，比如各个公司可能是不同的 community，而每个公司内部的角色大致是相同的(管理层和下属员工)。公司(community)内个体间会有比较密切的联系，但公司间相同职位(角色)的个体并不一定会有关联。

此时，我们提取某一个节点周围的graphlets子图个数，就可以构建一个向量，称为Graphlet Degree Vector(GDV)，如下图所示：

计算u节点的GDV

• u节点周围的子图总共能够组成3种graphlets，包含4种节点角色(a,b,c,d)
• 然后分别数u周围的角色节点a、b、c、d都有多少个，c=0是因为:在u节点邻域的信息中，u没有扮演c-d结构中c角色的作用
• 此时的[2,1,0,2]就是u的GDV

因为5个节点的子图能够有73种节点角色，所以就是一个73维的向量，可以很全面的表示图中的拓扑连接结构，通过比较两个节点的GDV我们就可以计算两个节点的距离和相似度

小结

节点级别的特征：

• 节点的重要度信息
  • 节点度数
  • 不同的节点centrality衡量方法

• 节点的结构信息
  • Node Degree
  • Clustering coefficent聚集系数
  • Graphlet构造子图

使用本小节的知识我们能够区分如下图左边形式的图中的节点（哪些是边缘，哪些是中心），但是无法区分右边所示的社群的概念（抱团），这部分区分需要后续的图神经网络的方法来完成

2. 连接层面的特征工程

Link-Prediction：通过已知连接补全未知连接，生成连接层面的D维向量有如下两种思路：

• 直接提取link的特征，把link变成D维向量
• 把link两端节点的两个D维向量拼在一起变成一个2D维的向量或者一个2行D列的矩阵

更鼓励使用第一种方式，因为第二种方式会丢失link本身的连接结构信息，而第一种方式直接提取link的特征之后我们就可以直接输入到下游的任务中去进行预测，看看两个节点之间是否有哪些类别

任务：基于已知边，预测新边的类别。测试模型时：将每一对没有连接的节点对进行排序，取存在连接概率最高的topK个节点对，作为预测的结果。

Link-Prediction的任务可以分为两种：

• 客观静态图，例如：
  • 蛋白质结构
  • 分子
  • 可以尝试把已经客观存在的部分删掉再去预测出来
• 随时间变化的，例如：
  • 网站论文的引用
  • 社交网络
  • 我们需要从一个时间段中的图去预测出下一个时间段的图中的连接，并且找到预测的连接中top-n的连接
  • 在用预测出来的top-n个连接和下一个时段真实的连接作比较

2.1 连接层面的工作

总结上面提到的连接层面的工作不论是静态的还是动态的，都是如下几个步骤：

• 提取连接特征 -> D维向量 -> 输入机器学习模型中，打一个分
• 然后从高到低降序排列分数，得到top-n
• 再去比较这top-n和真实值的区别

2.2 连接层面的特征

连接层面的特征可以分为：基于两节点间距离、基于两节点局部连接信息、基于两节点在全图的连接信息

• 基于两节点的最短路径长度

• 基于两节点局部连接信息
  • 例如两节点的共同好友个数
  • 两节点的交并比
    • 两节点邻域节点的交集，比上邻域节点的并集
  • 共同好友是不是社牛
    • 共同好友的连接数的倒数求和
    • 如果共同好友是个社牛，那么两个节点之间的连接就显得不重要（分母大使得整体变小），如果共同好友是个社恐，那么两个节点的连接就显得很坚实了。
  • 缺点：当两个节点没有共同好友时，各项局部连接的指标计算结果都是0，所以我们通常需看全图的信息。

• 基于两节点在全图的连接信息
  • Katz index卡兹系数：表示节点u和节点v之间长度为k的路径个数
    • 用邻接矩阵的幂运算
    • 离散数学中提到，邻接矩阵的n次幂表示的就是路径长度为n的路径（假设每条路径长度均为1）

如下图所示表示了k=1和k=2的计算结果：

节点u和节点v之间长度为k的路径个数就是Auvk矩阵的第u行第v列元素

• 卡兹系数的具体计算，如下图所示
  • 考虑到随着距离的增大，关系可能会变弱，所以添加了β（折扣系数）
  • 求和的过程就是一个等比数列求和
  • 参考高等数学中的几何级数知识，将其写成后面的形式

3. 全图层面的特征工程

将全图提取的特征表示为一个D维的特征向量，并且这个特征向量可以反映全图的结构特点

3.1 Bag-of-*

• Bag-of-Words(BoW)

对于全图提取特征其本质仍然是：数数（数不同特征在图中存在的个数）。类比在自然语言处理NLP中的一种思想Bag-of-Words(BoW)，将一个文章的内容全都列出来，然后去数里面每一个词/字出现的次数，这样我们就可以把一篇文章表示为一个D维的向量，其中每一维都是每一个词的次数，这样就可以把向量输入给计算机进行处理。

同理，对于图，我们可以把图看作文章把节点看作单词，只看每个节点有没有出现而不考虑连接结构，使得两个完全不同的图最终的编码结果是一样的，这是不可行的。

• Bag-of-Node degrees

一种改进想法：使用Bag-of-Node degrees，只看节点的连接数不看连接结构，最终效果是确实可以区分之前的两个结构不同的图，如下图所示

同理我们也可以把这种Bag-of-*的思想推广到其他的特征中去

3.2 Graphlat

• Bag-of-Graphlats

如下图所示，对于3个节点组成的graphlat从全图角度分析有四种（即，节点之间可以没有连接），对于4个节点组成的graphlat就有11种。我们就可以将全图的graphlat总结出来作为D维特征。

• 与之前的节点层面的特征不同的是
  • 可以有孤立节点
  • 从全图来数graphlat个数而不是计算节点邻域内的graphlat个数

如下图所示，假设全图中共有nk个graphlat那么，最终就会构造出nk维的特征向量，其中第i个表示的就是第i个graphlat在全图中的个数

如果把两张图的graphlat的特征向量做数量积，就可以得到两张图的kernel，这个kernel是一个标量，可以反映出两张图是否相近，是否匹配。如果两张图的graphlet尺寸不匹配，需要一个归一化操作使其大小变成相同量级，避免计算结果产生歪曲。

不经常使用这种Graphlat构造子图方式的原因主要是，这种方式比较消耗硬件（从原图中枚举寻找子图），是一个nk多项式量级的复杂度，k越大，复杂度越高，也就是一个N-P难问题

3.3 Weisfeiler-Lehman Kernel

一种性能上更加优化的kernel，使用颜色微调的方法迭代地丰富“节点词库”

案例如下：

• 左图是假设都是一种颜色1，每个节点表示的就是当前颜色，和自己相连的节点的颜色，例如G1中的左上角节点颜色为1并且和三个颜色为1的节点相连，所以表示为1,111
• 右图是将左图中的结果用了不同颜色来表示的结果，这个过程称为哈希（每一种颜色都有自己的编号—编号就是那个1,1…）

不断重复上述过程，发现之前的颜色又开始发生变化，观察发现G1中最下面两个节点由于结构完全一致，所以颜色一直相同，但是G2最下面的两个节点由于结构不一致，所以颜色不再是第一次哈希之后的相同值。

到这里我们经过两次哈希得到了13种颜色，也就是两张图均用13维的向量表示。我们就可以开始计算kernel求两张图的内积。

13维向量：针对每一种颜色计算对应的节点个数，有一些向量的元素为0，但是既然他有这种颜色，说明在另一张图中出现，即另一张图中他至少为1。

Weisfeiler-Lehman图核就是拿这两个特征描述向量的数量积作为两个图相似性的返回值，Weisfeiler-Lehman Graph Kernels 方法提出用WL子树核衡量图之间相似性。该方法使用WL Test不同迭代中的节点标签计数作为图的表征向量，它具有与WL Test相同的判别能力。在WL Test的第k次迭代中，一个节点的标签代表了以该节点为根的高度为k的子树结构。

该方法的思想是用WL Test算法得到节点的多层的标签，然后我们可以分别统计图中各类标签出现的次数，存于一个向量，这个向量可以作为图的表征。两个图的表征向量的内积，即可作为这两个图的相似性估计，内积越大表示相似性越高。

内积结果为：6x6+2x2+1x1+2x2+1x1+0x1+2x1+1x0+0x1+0x1+0x1+2x0+1x1 = 49，这个49就是这两张图的Weisfeiler-Lehman Kernel

用算法表示就是如下图所示：

这种方式的计算是和节点、连接呈线性关系，所以计算起来是非常方便的。而且Weisfeiler-Lehman Kernel与图神经网络GNN是非常类似的。

3.4 Kernel Methods

Kernel Methods核方法经常用在图机器学习中，因为经常需要用两个图来作比较（两张大图、一张大图和子图等等）。

kernel值是一个标量，这时候就用这个kernel值来代表两张图的结构，而不是用一张图的向量来表示。有了kernel之后一些现成的带有核函数的机器学习方法就可以直接拿来使用，比如Kernel SVM支持向量机。

3.5 其他的kernel

• Random-walk kernel
• Shortest-path graph kernel
• 等等

这些都是在统计机器学习时代的方法，现在是深度学习、神经网络的年代了。

总结

上述的特征工程提到了不管是上面提到的节点层面的特征还是连接层面的还是全图层面的，这些都是需要人工去设计，再输入到机器学习模型中的，对于特征的回顾如下图所示：

在后面要学习的的图神经网络中，我们就是端到端的用深度学习的方法，使用图嵌入自动得到图中的特征（包括结构、连接、语义特征等等），不再需要人工设计特征。

学习资料

官方课程

同济子豪兄-中文精讲视频

https://github.com/lyc686/CS224W_notes/

https://github.com/shenhao-stu/CS224W-Fall2021

https://andyguo.blog.csdn.net/article/details/128925380