一、图的特征
图点本身就具备的特征称为属性特征（如：连接权重、节点类型等），属性特征大部分时候都是多模态的。
图中一个节点和其他节点之间的连接关系称为连接特征(结构信息)
人工提取并构造的特征称为特征工程。（将图变为向量）特征工程一般针对图的连接特征进行构造
二、节点层面的特征工程
一般而言，节点层面连接特征分为：
①节点的连接数
②节点的重要度
③节点的聚集系数(某节点与其相邻节点之间是否有联系)
④节点的子图信息（某节点周围有多少人工定义的子图）
1.节点连接数
若求节点连接数，直接按某行/某列求和即可；或将邻接矩阵与一个值为1的向量相乘即可。但节点连接数不考虑连接的质量，所以引入下面三个指标来衡量节点连接的质量。
2.节点重要度
①特征向量重要度(Eigenvector Centrality)
某节点的重要度=与其相邻节点的重要度之和，公式表示为：
其中仅用于归一化
因为其是一个递归算法，实际计算转换为求邻接矩阵A矩阵的特征向量的问题
其中c为邻接矩阵A的特征向量（由与该节点相连的所有节点的重要度组成）；邻接矩阵A用以表示这些节点的连接属性；即为目标节点的重要度。
②介数重要度(Betweennness Centrality)
用以衡量一个节点是否处在交通咽喉处；计算方法为：对连通域中除了要求的节点外的所有节点，求其最短距离中有多少个必须经过该节点。如下图：
，而（路径为：A-C-B、A-C-D、A-C-D-E）
3.集群系数(Clustering Coefficient)
计算方法为：该节点的周围节点之间相连数 / 该节点与周围节点相连数，值域为[0,1]...(简单点理解就是三角形的个数)。详见下图示例：
计算结果分别为：、、
这种三角形连接被称为：自我中心网络(ego-network)
4.graphlet
相同样的节点数构成非同形子图（类似同分异构体），例如4个节点可以构成6种graphlet。
提取某节点周围的graphlet个数即可构成一个称为Graphlet Degree Vector(GDV)，如下图所示：
节点u可能出现的子图形式有三种，分别列出含有u节点的子图类型
GDV可以描述节点u的局部邻域拓扑结构信息。
三、连接层面的特征工程
目的：通过已知连接补齐未知连接。可以通过两种方法来获取D维向量：
①直接提取连接的特征
②将连接两端节点的D维向量拼在一起(但这种方法会丢失link本身的连接信息)
连接预测的一般方法为：
①获取连接的D维向量
②将D维向量送入机器学习中进行计算，获得分数
③将分数进行排序，选出最高的n个新连接
④计算这n个预测结果与真实值
1.连接特征
连接特征一般分为：①节点间的距离；②节点局部连接信息；③节点在全图的连接信息
①最短路径长度
即两个点之间经过节点最少的路径上的节点数，但是其与节点连接数一样只看数量不看权重。
②基于两节点的局部连接信息
共同相邻节点个数；交并比等。但若两个节点不存在局部连接，则其交并比和共同相邻节点个数均会为0。例如下图中A和E就不存局部连接。
③卡兹系数(Katz index)
表示节点u和节点v之间的长度为k的路径个数。计算方法：使用邻接矩阵的幂来计算，如下：
此式的实际意义为：=与u隔1步的邻居i；=i是否与v隔1步
由数学归纳法可知：长度为 的矩阵为（矩阵的 次方中第u行第v列的元素）
卡兹系数公式可以通过矩阵几何级数化简为：
其中为折减系数，位于0到1之间；为单位矩阵。
四、全图层面的特征工程
目的是提取整张图的特征，将其变为D维向量，反映全图结构特点。
实际就是在计算不同特征在图中存在的个数（将图视为文章，节点视为单词--Bag-of-Nodes）
但这种方法有一个缺陷，就是只看是否存在第 i 个节点而不关心连接结构，如下图中两个图编码的D维向量一致，均为[1 1 1 1]
还可以使用Bag-of-Node-degrees，但是同样的只看node dgree，不看节点也不看连接结构
Bag-of-xxx可以推广到之前提到的任意特征中，比如将全图的graphlets作为应用场景，其相较于节点层面的graphlets有如下区别：①可以存在孤立节点；②计数对象为全图，而不是特定节点邻域。
将两张图的graphlet进行数量积则可得到Graphlet Kernel(一个标量)，该指标可以反映两张图是否相近/匹配，公式记作：
若两张图尺寸不一致则需要对其进行归一化
但是这种做法对算力的消耗极大。故一般采用Weisfeiler-Lehman Kernel算法，采用的是颜色微调的思想(Color refinement)，其具体做法如下：
①将图初始化一个有一个编码
②根据具体节点的连接数量，对其编码进行调整
③将不同的编码以不同的颜色代替（Hash）
以上步骤可以重复进行，最后两个相同结构的节点颜色始终相同
这样就将每张图变成了一个维度较低的向量。将这两张图的向量求内积即可得到Weisfeiler-Lehman kernel
上述操作可以记作：, k 表示上述编码过程进行了 k 步，表示捕获了图中 k 跳个连接
参考阅读
您阅读本篇文章共花了：
发表评论