图机器学习的传统方法
传统图机器学习流程
传统图机器学习流程可分为以下四步：
- 第一步是根据不同的下游任务为节点/链接/图的人工设计特征（hand-designed features）
- 第二步是将我们设计特征构建为训练数据集
- 第三步是使用训练数据集训练一个机器学习模型，常见的有随机森林，SVM和神经网络等
- 第四步是使用训练好的的模型完成新样本的预测任务
从上面的步骤中我们可以发现，在传统图机器学习中模型性能好坏很大程度上取决于人工设计的图数据特征（hand-designed features）。
下面总结针对图机器学习三大下游任务中特征设计的各种方法，为了简单起见，主要关注于无向图。
节点级任务和特征设计
节点级任务主要是预测未带标签节点的label。
针对节点级任务的特征设计目的是描述网络中节点的结构和位置。
常见的特征有：
- 节点度数（Node degree）
- 节点中心性（Node centrality）
- 聚类系数（Clustering coefficient）
- Graphlets
节点度数（Node degree）
在无向图中，某个节点的度等于与该节点直接相连节点的数量；在有向图中还需要考虑入度和出度。
由于度不考虑节点的重要性，即认为每个节点都同等重要，故节点中心性（Node centrality）被用于考虑节点的重要性的场景。
节点中心性（Node centrality）
节点中心性的分类主要有：
- 特征向量中心度(Engienvector centrality)
- Betweenness centrality
- 聚类系数(Closeness centrality)
特征向量中心度(Engienvector centrality)
每个节点的centrality与该节点所有邻居节点的centrality总和正相关。节点
v
v
v的特征向量中心度
c
v
c_v
cv的定义为：
上述定义可改写为矩阵形式，最大特征值对应的特征向量即为节点的特征向量中心度
c
m
a
x
c_{max}
cmax：
Betweenness centrality
Betweenness centrality指标的核心思想是：某个节点
v
v
v在其他任意两个节点
s
s
s和
t
t
t的最短路径上的比例。
Closeness centrality
如果一个节点到所有其他节点的最短路径长度较小，则该节点很重要。
聚类系数(Closeness centrality)
节点
v
v
v的聚类系数(Closeness centrality)定义为：
Graphlets
链接级任务和特征
链接级任务主要目的是通过学习现有的边用于预测新的边。
链接级任务可分为以下两种：
边预测主要流程为：
链接级任务特征主要可以分为以下几种：
- 基于距离的特征（Distance-based feature）
- 局部邻域重叠度量Local neighborhood overlap）
- 全局邻域重叠度量（Global neighborhood overlap）
基于距离的特征（Distance-based feature）
下面展示的是基于最短路径特征，其缺点是不能捕获共享节点（重叠节点）的度。
局部邻域重叠度量（Local neighborhood overlap）
局部邻域重叠度量缺点是若两个节点没有共同的邻居，则度量标准始终为零。然而这两个节点之间可能仍然会存在边。
全局邻域重叠度量（Global neighborhood overlap）
Katz index
Katz index：利用图邻接矩阵的幂计算给定节点对之间所有长度的路径数。
其他可参考Katz 指标（The Katz Index,KI）的讲解与详细推导
整图级任务、图核函数和特征
核方法（Kernelmethods）广泛应用于传统的图机器学习图级预测任务。