使用图进行特征提取：最有用的图特征机器学习模型介绍

从图中提取特征与从正常数据中提取特征完全不同。图中的每个节点都是相互连接的，这是我们不能忽视的重要信息。幸运的是，许多适合于图的特征提取方法已经创建，这些技术可以分为节点级、图级和邻域重叠级。在本文中，我们将研究最常见的图特征提取方法及其属性。

注意:我的文章结构类似于William L. Hamilton[1]所写的图形学习书籍。

节点级别的特征

从图中获取信息的最简单方法之一是为每个节点创建单独的特性。这些特征可以利用迭代方法从一个较近的邻域和一个较远的K-hop邻域捕获信息。让我们开始吧!

节点的度

为了计算节点度，将关联边的数量计算到Vr中。

节点度是一个简单的度量指标，可以定义为关联到节点的边数。数学上可以定义为:

节点度方程[1]

其中A是邻接矩阵，du是节点u的一个度。这个度量常被用作算法的初始化，用于生成更复杂的图级特征，如weisfeler - lehman核。

特征向量中心

不同的中心。左图说明了特征向量的中心。右图显示了度的中心。

特征向量中心性度量考虑了2个方面:

• 节点u的重要性
• 节点u的相邻节点的重要性

换句话说，具有高特征向量中心性的节点应该有许多与其他节点高度连接的邻居。

这个度量背后的数学是基于使用矩阵方程的递推算法，相当复杂。我没有告诉你这个数学方程的细节，但如果你对此感兴趣，[1]对这个话题有一个很好的解释(第19页)。

集聚系数

计算每个红节点的聚类系数

直观地说，我们可以把这个度量看作是节点组之间连接的紧密程度。它测量节点[1]邻域内闭合三角形的比例。节点u的聚类系数可定义为:

聚类系数方程，摘自[1]

其中(v1、v2)∈Ɛ意味着节点v1、v2之间的联系。v1和v2被定义为与节点u相邻的任意节点对。

我们可以说它是相邻节点之间的边数与节点的相邻节点数(节点度)[1]的比值。当值接近1时，表示节点u的所有邻居都是相连的(图中左侧的黄圈)，当值接近0时，表示节点的邻居之间几乎没有任何联系(图中右侧的黄圈)。

DeepWalk

DeepWalk以一个图形作为输入，并在R维度中创建节点的输出表示。看看R中的“映射”是如何将不同的簇分开的。

它是一种基于学习的方法，将一个图作为输入，并学习节点[4]的表示和输出。它将语言建模中使用的技术重新应用到图形领域。该算法主要包括两个部分:

• DeepWalk
• SkipGram

在DeepWalk中，我们使用一个随机生成器来生成节点的短序列。然后，SkipGram使用生成的节点序列将节点编码到低维空间中。

DeepWalk算法有点难以理解，所以我建议看看他们的原始论文（http://www.perozzi.net/publications/14_kdd_deepwalk.pdf）

图的层次特性

如果我们想要获取整个图的信息，而不是查看单个节点，该怎么办呢?幸运的是，有许多可用的方法可以聚合关于整个图的信息。从简单的方法，如邻接矩阵，到更复杂的内核，如weisfeler - lehman内核，或基于路径的内核。从图中提取全局信息的方法有很多种;在本节中，我们将探讨最常见的一些。

邻接矩阵

邻接矩阵是一个稀疏矩阵，其中“1”表示两个节点之间存在连接。

这是一个常见的特征。是一个稀疏矩阵，它包含关于两个节点之间连接的信息。如果有“1”，则表示两个特定节点之间存在连接。矩阵中的a_ij元素中i是行，j是列，表示节点Vi和Vj之间是否有连接。

拉普拉斯矩阵

拉普拉斯矩阵包含与邻接矩阵相同的关于连通性的信息，但方式略有不同。简单定义为:

拉普拉斯算子的矩阵方程。L -拉普拉斯矩阵，D度矩阵，A -邻接矩阵

式中，L为拉普拉斯矩阵，D为度矩阵，A为邻接矩阵。度矩阵是一个简单的对角矩阵，对角线上的每个元素表示每个节点有多少个邻居。

节点的度量

它不是一个单一的度量，而是一种类型。它背后的算法非常简单——我们只是以[1]的某种方式聚合节点级别的特性。例如，我们可以取节点度数的平均值，或者取边缘连接的直方图。

Weisfeiler-Lehman内核

WL内核是对节点度量方法的改进，在这种方法中，我们从节点的邻近点迭代地聚合信息[1]。

该算法可归纳为以下几个步骤[1]:

• 为图中的每个节点设置一个初始标签，例如节点的度数
• 使用邻域的散列标签，通过迭代为每个节点分配新标签
• 经过K次迭代，我们现在已经收集了K-hop邻域的信息。然后我们可以使用任何类型的节点度量来总结这些新标签

这个内核在化学信息学中应用非常广泛，它经常应用于分子数据。例如，循环指纹算法就是基于WL核的。

Graphlet内核

从图中计算所有可能的核大小为3的图。

Graphlet构造大小k∈{3,4,5}的小子图。graphlet内核背后的思想很简单:遍历所有图可能是一个NP难问题，因此通过其他的技术，比如对固定数量的图形进行采样，以降低计算复杂度[5]。在数学上，graphlet kernel定义如下:

graphlet内核的定义。G - 图, G ' - 另一张图, f_G -向量，其中第i个分量对应于graphlet_i的出现。

G和G '是我们可以比较的不同的图。f_G和f_G '是向量，其中第i个元素对应于某个graphlet_i[5]的出现频率。我们可以将这些向量归一化，以考虑较小尺寸的图形[5]的较高频率计数:

Graphlet核在生物信息学和化学信息学中被广泛使用，在这些领域中，了解用图表示的分子中某些子结构出现的频率特别有用。

基于路径的内核

基于路径的核通过在图的标记节点和边缘上应用随机漫步或最短路径来创建特征向量[7,8]。这个内核的算法与graphlet内核类似，但是我们研究的不是graphlet，而是图中的不同路径[1]。使用随机漫步的基于路径的内核将检查随机生成的路径。那些基于最短路径的，只研究连接两个节点的最短路径。

优秀算法

还有更多的算法/模型可以创建图形级别的特性。其他包括GraphHopper内核、神经消息传递或图卷积网络。

社区重叠特征

节点级和图级特性无法收集邻近节点之间的相关信息[1]。邻域重叠特征帮助我们预测两个节点之间是否有连接及其类型，并测量了图中局部和全局的重叠。

区域重叠

局部重叠度量是量化两个节点之间邻域的相似性的度量。这些度量标准中的大多数都非常相似，只是在标准化常数方面略有不同[1]。

例如，节点u与v之间的Sorenson索引计算公式如下:

节点u和v之间的索伦森指数方程中的分子计算这些节点之间的共同邻居。分母是一个标准化常数，是节点度数的总和。

分子项计算这些节点之间的共同邻居。分母项(d_u + d_v)/2是节点度数的平均值。

另一个度量标准，如Salton索引、Hub提升索引或Jaccard索引与Sorensen索引的不同之处在于标准化常数。

一个稍微不同的度量是资源分配(RA)索引。它度量了节点u和v之间共同邻居的重要性[1]。它是通过对所有共同邻居的节点度的倒数求和来实现的。

资源分配索引。

全局重叠

全局重叠度量检查节点是否属于图中的同一个社区。

如果某些节点属于图中的同一社区，则全局重叠度量将获取该信息。我们不再只关注两个相邻的节点，而是查看来自更遥远的邻域的节点，并检查它们是否属于图中相同的社区。

常用的方法之一是Katz索引，它计算两个特定节点之间所有可能的路径:

Katz索引。

邻接矩阵A有一个有趣的性质。它的i次幂表示在两个节点u和v之间是否有一条长度为i的路径[10]。β一种标准化常数，在这里我们可以选择路径长度(即短或长)。

节点的度越高[1]，Katz指数就会产生越高的相似度得分。为了克服这一问题，提出了考虑这种偏差的LHN相似度度量:

LHN相似性度量。

该度量通过邻接矩阵的期望值进行标准化。

总结

我们已经看到了可以从图中提取的三种主要类型的特征:节点级、层次级和邻域重叠特征。节点级特征(如节点度)或特征向量中心性为每个单独的节点生成特征，而图级特征(如WL或Graphlet内核)从整个图中捕获信息。邻域重叠特征，例如，Sorensen索引或LHN相似性，创建了度量两个节点之间共同邻域的特征。

在本文中，我总结了最流行的图形特征提取方法。当然，还有很多，我没有在这里说。如果你想深入了解这个话题，你可以在参考资料部分找到非常有用的文献:)

感谢您阅读本文。我希望这对你有用!

引用

[1] Graph Representation Learning Book by William L. Hamilton

[2] On Node Features for Graph Neural Networks

[3] Survey on Graph Kernels

[4] DeepWalk: Online Learning for Social Representations

[5] Efficient graphlet kernels for large graph comparison

[6] Graphlet Kernels (ETH Lecture Notes)

[7] Marginalized Kernels Between Labelled Graphs

[8] Shortest-path kernels on graphs

[9] Community structure in social and biological networks

[10] Katz Centrality within a social network.)

作者：Kacper Kubara

deephub翻译组：孟翔杰