【斯坦福CS224W】图机器学习图神经网络-Task02下-传统图机器学习的特征工程_卡兹系数

参考资料：
开源内容：https://github.com/TommyZihao/zihao_course/tree/main/CS224W
B 站视频：https://space.bilibili.com/1900783/channel/collectiondetail?sid=915098

大佬笔记：lyc686 (lyc learning ...) · GitHub

人工特征工程和机器学习

由于计算机看不懂图，只能看懂向量和矩阵等等
因此，我们需要把节点的特征写为向量（把节点作为d维向量 ）；连接的特征写为向量；子图和全图的特征写为向量。将向量输入到机器学习特征中，就可以进行学习。

属性特征和连接特征 

• 属性特征：比如银行风控用户节点的属性特征 有收入 学历 年龄 婚姻状况等 
• 连接特征：就是这个节点 在一张图中 与其他节点的连接关系。

我们今天只讲连接特征 

什么是特征工程？

比如我们使用四维向量花瓣长度，花瓣形状等等四种特征，去判断燕尾花的种类。我们能不能构造一个新的特征？这些特征能够让算法能够更好的区分。更容易去预测。这就称之为特征工程。

例如，解决一个异或问题。

观察x轴，y轴都不能解决问题，但是可以找到一个新的特征，x×y就可以直接得到它的种类。数据和样本都是原来的，但是加了一个特征就可以大大方便算法进行了预测。这就是特征工程的重要性。

选对特征很重要，你的数据集和特征特别好，哪怕你的模型不好，也能够跑出不错的数据。

我们今天讲如何对节点，对连接，对全图 人工去构造特征。尽管构造出的特征有的好，有的不好，只需要交给算法去处理。算法会将好的特征给予更高的权重，不好的特征给予更低的权重。是不用我们担心操控的。我们的任务仅仅是构造出这些特征。这个过程就称为特征工程。

在一些大的竞赛中，经常能看到选手大多不是集中在神经网络调参，或是选一个比较好的算法，而是在根据实际的领域，根据人类的专家知识构造特征，构造一些尽可能有用的特征。

为了便于理解今天的课程，都是在无向图的基础上进行的。

节点层面的特征工程

输入某个节点的d维特征，输出该节点是某类的概率。最关键的就是要将这个d维特征构造好。

以节点分类为例。以银行信用卡欺诈为例，我们已知这张图红色的是欺诈，绿色的是没有发生欺诈，还有一些未知的。经过半监督节点分类，我们就可以得到一个预测。

构造D维特征

一些可以考虑的角度：

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

（1）节点连接数（数连接数）

如上图所示，如果只看节点连接数，那么下图中A、G节点的特征是相同的，但是两个节点所处的圈子的质量是完全不同的（一个是院士的关门弟子、另一个是一个人旗下的博士）

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

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

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

（2）节点重要度

同时考虑节点的重要度（质量），有如下方法

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

  • 

  • 如上图所示求和将λ乘到左边，就可以等价为求矩阵A的特征向量的问题，上图的公式可以做如下解释：
    • 如果图中一共有四个节点，那么c向量就是一个4行一列的向量，每一行都是一个节点的特征向量重要度
    • 等号右边等价于一个矩阵✖c向量
    • 矩阵A每一行对应的就是和当前节点相连的边的数量，和c相乘就是左边的每一个节点的特征重要度求和的意思
    • 此时c向量就是矩阵A的特征向量，λ就是矩阵A的特征值
  • 可以思考Eigenvector centrality和PageRank的区别与联系
• Betweenness centrality（中介中心性）
  • 中介中心性用于刻画一个节点是否处于交通咽喉（必经之地）
  • 计算案例如下图所示：

  • 

  • 如上图算C节点的中介中心性
    • 除了C节点之外其他四个节点的两两组合就会有C42=6
    • 计算这六对的最短距离，有哪些一定要经过C
    • 最终带入公式就能计算出节点v的链接中心性
  • 例、湖北（从湖北到其他任意一个省，最多跨两个省）、马六甲海峡等等
• Closeness centrality（连接中心性）
  • 连接中心性刻画了一个节点是否去哪儿都近
  • 计算案例如下图所示：

  • 

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

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

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

计算案例如下图所示：

此对数非log，而是连接对数量

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

（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我们就可以计算两个节点的距离和相似度

补充：在NetworkX中子图称为Atlas

小结一下：

节点的重要度信息可以看：

• Node Degredd
• 各种的centrality

节点的结构信息可以看：

• Node Degree
• Clustering coefficent聚集系数
• Graphlet构造子图

除此之外还有：

• PageRank
• Katz Centrality
• HITS Hubs and Authorities

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

连接层面的特征工程

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

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

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

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

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

（1）连接层面的工作

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

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

（2）连接特征分类

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

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

  • 类似Node Degree这种方式只看最短路径的长度，但是忽视了个数和通路的结构

  如下图所示：

  

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

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

  如下图所示：

  

• 基于两节点在全图的连接信息

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

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

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

  

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

全图层面的特征工程

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

（1）Bag-of-*

• Bag-of-Words(BoW)

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

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

• Bag-of-Node degrees

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

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

（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）Weisfeiler-Lehman Kernel

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

案例如下：

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

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

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

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

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

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

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

（4）Kernel Methods

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

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

（5）其他的kernel

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

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

总结

本次任务从图的基本表示开始，学习了各种不同类型的图（无向图、有向图、异质图、二分图），还学习了图的一些基本表示（邻接矩阵、连接表、邻接表）以及一些图的连通性问题。之后的特征工程提到了不管是上面提到的节点层面的特征还是连接层面的还是全图层面的，这些都是需要人工去设计，再输入到机器学习模型中的，对于特征的回顾如下图所示：

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