????????在使用特征的过程中，能够用到的模型包括随机森林，SVM，神经网络等。在传统的机器学习中，特征的提取是一个关键问题，在图机器学习中同样如此，本章的重点就是如何确定图的特征，包括节点层面，边层面以及图层面，除了特征提取之外还有一些与特征应用相对应的预测任务。为了简单起见，我们主要关注无向图。

下面开始吧！

节点层面特征

节点特征的作用，即刻画图中节点的结构和节点的位置。

节点特征的分类：

节点度
节点中心度（Node Centrality）【这里的中文翻译可能不准确，也没找到其他的好的翻译】
集聚系数（Clustering Coefficient）
Graphlet

节点度

????????节点 $v$ 的度 $k_v$ 为节点拥有的边数。

????????性质：将一个节点周围所有的边都平等对待。

节点中心度（Node Centrality）

????????节点中心度 $c_v$ 将图中不同节点的重要性考虑进来。节点中心度（Node Centrality）的有以下三种重要的模型：

特征向量中心度（Engienvector centrality）

????????如果节点 $v$ 周围的节点 $u\in N(v)$ 是重要节点，那么节点 $v$ 也是重要的节点（有点递归的味了）。我们将节点 $v$ 的中心度 $c_v$ 建模为邻居节点的中心度的和，其中 $\lambda$ 为正常数：

? $c_v=\frac{1}{\lambda}\sum_{u\in N(v)}{c_u}$

更确切些 $\boldsymbol{c}=\left[ \begin{matrix} c_1& c_2& \cdots& c_N\\ \end{matrix} \right] ^T$ . 我们可以看到上式变成了求解矩阵特征向量的形式。根据Perron-Frobenius Theoremp[1]最大的特征值 $\lambda _{\max}$ 总是正数且唯一，那么 $\lambda _{\max}$ 对应的特征向量也是唯一的，我们可以将其作为中心度 $\boldsymbol{c}_{\max}$ .?

中介中心度（Betweenness centrality）

????????如果一个节点位于其他节点之间的许多最短路径上，那么它就是很重要。

$c_v=\sum_{s\ne v\ne t}{\frac{\#( \mathrm{shortest} \mathrm{paths} \mathrm{betwen} s\,\,\mathrm{and} t\,\,\mathrm{that} \mathrm{contain} v)}{\#( \mathrm{shortest} \mathrm{paths} \mathrm{between} s\,\,\mathrm{and} t)}}$

紧密度（Closeness centrality）

????????如果一个节点到所有其他节点的最短路径长度很小，那么这个节点就很重要。

$c_v=\frac{1}{\sum_{u\ne v}{\,\,\mathrm{shortest} \mathrm{path} \mathrm{length} \mathrm{between}}u\,\,\mathrm{and} v}$

集聚系数（Clustering Coefficient）

?????????测量 $\mathcal{V}'S$ 的邻居节点的连接程度

$e_v=\frac{\#( \mathrm{edges} \mathrm{among} \mathrm{neighboring} \mathrm{nodes} )}{\left( \begin{array}{c} k_v\\ 2\\ \end{array} \right)}\in [0,1]$

????????

集聚系数计算图中三角形的个数占 $\left( \begin{array}{c} k_v\\ 2\\ \end{array} \right)$ 的比例。

?Graphlets

????????现在将计算三角形个数（Clustering Coefficient）拓展到计算预先确定子图的个数，即Graphlets。

????????Graphlet: 有根的连通非同构子图[2]。这里的根，在后面的例子中说明。

????????有了Graphlet的定义，现在考虑Graphlet Degree Vector (GDV)的概念，即基于Graphlet的节点特征，具体计算以节点 $v$ 作为根的Graphlet的个数。

????????如下图例子所示：

?????????一般来看3点的分同构连通子图的个数为2，但是这里是3，因为这里考虑了节点的根，graphlet集的c和d点分别作为根将导致不同的图。节点v的graphlet特征为[2,1,0,2]。

????????Graphlet Degree Vector (GDV)提供了一个测量节点局部网络拓扑的方法，此方法提供了一个相较于节点度特征和集聚系数更加详细的测量两节点相似性的方法

?????? 总结来看：此节提供了两中获取节点特征的策略，即为：

基于节点重要性的特征（对于预测图中重要性的节点很重要。如预测社交网络中的名人。）

节点度
不同节点中心度测量方法

基于图结构的特征（对于预测某个节点在网络中扮演的角色很重要。如在蛋白质-蛋白质网络中预测某个蛋白质的功能。）

节点度
集聚系数
Graphlet Degree Vector (GDV)

?边层面的预测概览

????????主要目的是基于现有的边预测新的边。在测试阶段中所有的预测节点对都排好序，取前K个节点对作为预测结果。预测的关键是将对节点对设计好特征。

????????下面是两个边预测任务的描述：

随机删除某一个边

????????在边集中随机删除一个边，然后以预测该边作为任务目的。

时变的边

????????给定图 $G\left[ t_0,t_{0}^{'} \right]$ 到时刻 $t_{0}^{'}$ 的边，利用这些已知的边，输出一个有序的边集序列L作为 $G\left[ t_1,t_{1}^{'} \right]$ 时刻的预测。

????????评价标准：计算测试区间 $\left[ t_1,t_{1}^{'} \right]$ 所有新生成的边数M，然后按照排序法则将M个边进行排序，取前n个作为预测结果，然后判断预测结果与真实值的差异。

????????下面是具体方法，总体来看最重要的是如何给这些节点对排序。

重要的边特征

基于距离的边特征

最短路径特征

????????此特征没有捕捉到节点邻居的重叠程度。节点对(B, H) 共享两个邻居节点，(B, E) and (A, B)仅共享一个邻居节点。

局部邻居重叠

目的：捕捉节点对 $v_1$ 和 $v_2$ 之间共享的邻居节点。

全局邻居重叠

????????局部邻居重叠的局限性：如果两个节点没有任何共同的邻居，Metric总是0。然而，这两个节点在可能有潜在的邻居节点，比如2阶邻居。

????????全局邻居重叠通过考虑整张图来解决这个局限性。

全局邻居特征——Katz index方法

????????Katz index：计算给定节点对之间所有长度的路径数。

????????使用邻接矩阵的幂来计算两个节点对之间的所有路径。

证明：让 $P_{uv}^{\left( K \right)}$ 表示节点 $u$ 和 $v$ 之间长度为K的路径的个数。 $P_{uv}^{\left( 1 \right)}$ 表示节点 $u$ 和 $v$ 间长度为1路径个数，即节点 $u$ 和 $v$ 是直接邻居。

????????计算 $P_{uv}^{\left( 2 \right)}$ ：

????????Step 1: 计算所有节点𝒗邻居，即计算出𝒗一步能到达的所有节点 $i$ ，满足 $P_{uv}^{\left(1 \right)}$ 。

????????Step 2：计算出 $u$ 一步到达𝒗邻居节点的路径数之后。

$\boldsymbol{P}_{\boldsymbol{uv}}^{(2)}=\sum_i{\boldsymbol{A}_{\boldsymbol{ui}}}*\boldsymbol{P}_{iv}^{(\mathbf{1})}=\sum_i{\boldsymbol{A}_{ui}}*A_{iv}=A_{uv}^{2}$

????????按照此种方式可以证明 $P_{uv}^{\left( K \right)}=A_{uv}^{K}$ .

因此节点 $v_1$ 和 $v_2$ 的Katz index的计算公式为：

????????Katz index 的闭式表达为（可以直接按照等比数列求合的方式计算）

边层面特征的总结为

????????

基于距离的边特征
1. 使用两个节点之间的最短路径长度，但不捕捉邻居如何重叠
局部邻居重叠
1. 获取两个节点共享多少个相邻节点
2. 当没有共享邻居节点时为零
全局邻居重叠
1. 使用全局图结构对两个节点进行评分
2. Katz index统计两个节点之间所有长度的路径个数之和

图层面的特征

目标：希望特征能够刻画整个图的结构。

有关核方法的介绍，没有看明白，直接贴上原PPT。感觉总体来看应该是一个二元函数，输入参数为两个数据（集），输出为相似度是一个实数。

图核

图核：测量两个图之间的相似性。

包括：

Graphlet Kernel [3]
Weisfeiler-Lehman Kernel [4]
还有一些其他的核方法
1. 随机游走
2. 最短路径图核

图核的主要思路（Key Idea）

????????目标：设计图特征向量 $\phi \left( G \right)$

????????主要思路：使用Bag-of-words（BoW）方法。

????????方法简述：BoW仅仅使用单词在文档出现的次数作为该词的特征(不考虑顺序)。

????????简单推广到图：将单词替换为节点。

????????如下所示，因为所设置的 $\phi \left( \cdot \right)$ 仅仅考虑图中红色节点的个数，所以两张不同的图得到了相同的特征。

??????? 如果使用bag-of-node degrees, 即使用节点度出现的次数作为特征。

能够区分出来这两张不同的图。

????????Bag-of-word / node / node degrees 这里的观测特征都可以随意改变，即概括来看Bag-of-*，*表示任意观测特征。不过Graphlet Kernel 和 Weisfeiler-Lehman kernel均是使用bag-of-*.

Graphlet Features

????主要思路：计算不同的Graphlets在图中出现的次数。

????注意：这里graphlets的定义有点不同于节点层的特征。

图层面的graphlet features 不需要是一个连通图（可以是）。
图层面的graphlet features没有根

如下图所示:

Graphlets Features实例计算

?给定图 G和一个 Graphlet list $G_k=\left( g_1,g_2,...,g_{n_k} \right)$ ，定义graphlet计算向量 $f_G\in \mathbb{R}^{n_k}$

$\left( \boldsymbol{f}_G \right) _i=\#\left( g_i\subseteq G \right) \,\,\mathrm{for} i=1,2,...,n_k$

?例如下图

????????

Graphlet Kernel

????????给定两个图 $G$ 和 $G'$ ，graphlet 核表示为

$K\left( G,G' \right) =\boldsymbol{f}_{G}^{\mathrm{T}}\boldsymbol{f}_{G'}$

是描述两个图的相似性。

Problem：如果两个图的大小不同（节点数量不同），那么这个核输出结果将有很大的偏差。

Solution：归一化取得的特征

$\boldsymbol{h}_G=\frac{\boldsymbol{f}_G}{\mathrm{Sum}\left( \boldsymbol{f}_G \right)}\quad K\left( G,G' \right) =\boldsymbol{h}_G^{\mathrm{T}}\boldsymbol{h}_{G'}$

局限性（Limitations）:计算graphlets花费计算量巨大。

在图大小为n中计算graphlets大小为k的特征需要列举 $n^k$ 次 .
判断子图是否与graphlets同构是一个NP-hard问题
如果图的节点度大小上限为d，计算大小为k的graphlets的计算复杂度为 $O\left( nd^{k-1} \right)$ .

因此需要一种高效的算法！

Weisfeiler-Lehman kernel

?目标：设计一个高效的图特征描述算子 $\phi \left( G \right)$

思路：使用邻居结构来迭代的丰富节点单词表。

广义版的包节点度，因为节点度是单跳邻域信息。

实现算法：颜色细化（Color refinement）

????????Color refinement

给定带有 $N$ 个节点的图 $G$ 。?

给每一个节点都分配相同的初始颜色 $c^{(0)}(v)$
通过

$c^{(k+1)}(v)=\mathrm{HASH}\left( \left\{ c^{(k)}(v),\left\{ c^{(k)}(u) \right\} _{u\in N(v)} \right\} \right)$

???????迭代的细化每个节点的颜色，其中HASH将不同的输入映射成不同的颜色。

在经过K步细化之后， $c^{(K)}(v)$ 总结了K跳邻居的结构信息。

下面是具体实例

第一步初始化各个节点的颜色

?第二步聚合邻居节点

聚合后的邻居节点使用HASH映射

一次新的迭代：

再一次迭代

????????最终的Weisfeiler-Lehman kernel 特征为下图，其中counts表示在整个迭代过程中，颜色所出现的次数。

????????WL核的最终结果由颜色计算向量的内积表示（如下图）

总结：

WL kernel 计算十分高效。
1. 每个迭代过程中的时间复杂度与边的数量呈线性相关。
在计算核值时，仅需要记录两个图中出现的颜色。因此颜色的种类是节点个数的上限。
计算颜色的种类个数的时间消耗与节点的个数成线性关系
总的来看，时间复杂度与边的数量成线性关系。

图层面特征总结

Graphlet Kernel
1. Graph 被表示为Bag-of-Graphlets
2. 计算代价大
Weisfeiler-Lehman kernel
1. 应用k步的颜色细化算法来细化节点颜色
  - 不同的颜色捕捉不同的k跳邻居结构
2. 图被表示为Bag-of-colors
3. 计算高效
4. 与图神经网络密切相关（后面会介绍）

章末总结：

传统的ML路线
1. Hand-crafted特征+ML模型
图数据上的Hand-crafted特征
- 节点层面
  1. 节点度、中心度（centrality）、集聚系数、graphlets
- 边层面（link-level）
  1. 基于距离的特征
  2. 局部/全局邻居重叠
- 图层面特征
  1. Graphlet kernel，WL kernel

[1] https://zhuanlan.zhihu.com/p/80952693

[2] 同构图的概念:

????????对两个图， $G=(V(G),E(G))$ 与 $H=(V(H),E(H))$ ，如果存在两个一一映射：