图学习任务
我们简单回顾下，上一节我们介绍了，图的机器学习任务主要是以下三种：
- Node Level:节点级别
- Link Level：边级别
- Graph Level：图级别
并且三部分难度依次是由浅入深的
传统ML流程
- 定义和设计节点/边/图的特征
- 对所有训练数据构造特征
- 训练ML模型
（1）随机森林
（2）支持向量机
（3）神经网络等
- 应用模型
给定一个新的节点、边、图，然后获取特征进行预测
我们总结下 基于Graph的机器学习相关概念和流程，首先明确下目标
目标：对一些对象集合进行预测，比如是分类或者回归任务
特征设计：
- 特征:
d-dimensional向量 - 对象：Nodes，edges，或者是graps
- 目标函数：结合具体任务设计目标函数，如下图所示给定一个图G(V,E)，其中V代表节点集合，E代表边集合，然后学习节点到向量空间R的映射函数，也就是我们要学习权重参数W
为了方便，我们下面的例子是基于无向图(undirected grpah)进行解释的。
节点级别的相关任务
基于图中带有标签的节点训练模型，然后预测未标注节点的标签，
在这里我们主要阐述下Node的四种特征：
- Node degree:节点的度
- Node centrality:节点的中度
- Clustering coefficient:相似性
- Graphlets:图元
节点的度
- kv代表是节点v与邻居节点相连边的个数
- 所有邻居节点都是相等的
如下图所示，A的度为1，B的度为2，C的度为3，D的度为4
节点的中心度 Node Centrality
- 节点的度只计算了相连节点的个数，但是没有评估节点的重要性
- 节点的中心度
考虑了节点在图中的重要程度 - 节点的中心度有很多种计算方式：
(1) Engienvector centrality:特征向量中心性
(2) Betweenness centrality:中介中心性
(3) Closeness centrality:紧密中心性
(4) 其他方式
Eigenvector centrality:特征向量中心性
- 如果一个节点的邻居节点们
越重要，那么该节点
就越重要 - 我们将节点𝑣的中心性建模为相邻节点的中心性之和：
其中
为一个正常数。 - 我们注意到上面的等式是通过递归的方式来计算度度中心性的，所有我们应该怎么求解
其中
为正常数，
为邻接矩阵，如果
,那么
- 我们可以看到度中心性是一个特征向量(eigenvector)，根据非负矩阵定理(Perron-Frobenius Theorem)我们可以知道
是一个正值并且是唯一的，特征向量
当做度中心性。
通常来说，有许多不同的特征值
能使得一个特征方程有非零解存在。然而，考虑到特征向量中的所有项均为非负值，根据佩伦-弗罗贝尼乌斯定理，只有特征值最大时才能测量出想要的中心性。然后通过计算网络中的节点
其特征向量的相关分量
便能得出其对应的中心性的分数。
特征向量的定义只有一个公因子，因此各节点中心性的比例可以很好确定。为了确定一个绝对分数，必须将其中一个特征值标准化，例如所有节点评分之和为1或者节点数 n。幂次迭代是许多特征值算法中的一种，该算法可以用来寻找这种主导特征向量。此外，以上方法可以推广，使得矩阵A中每个元素可以是表示连接强度的实数，例如随机矩阵。---特征向量中心性wiki
这里其实涉及到比较多的线性代数的理论以及矩阵分析的算法，我特意查了一些文章帮大家去回顾和理解下这里涉及到的知识：
(1) 线性代数之——特征值和特征向量
(3)非负矩阵
我们这里再通过文章谁是社会网络中最重要的人？解释特征向量中心性：
特征向量中心性的基本思想是，一个节点的中心性是相邻节点中心性的函数。也就是说，与你连接的人越重要，你也就越重要。
特征向量中心性和点度中心性不同，一个点度中心性高即拥有很多连接的节点特征向量中心性不一定高，因为所有的连接者有可能特征向量中心性很低。同理，特征向量中心性高并不意味着它的点度中心性高，它拥有很少但很重要的连接者也可以拥有高特征向量中心性。
考虑下面的图，以及相应的5x5的邻接矩阵(Adjacency Matrix)，A。
邻接矩阵的含义是，如果两个节点没有直接连接，记为0，否则记为1。
现在考虑x，一个5x1的向量，向量的值对应图中的每个点。在这种情况下，我们计算的是每个点的点度中心性（degree centrality），即以点的连接数来衡量中心性的高低。
矩阵A乘以这个向量的结果是一个5x1的向量：
结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值（连接数，点度中心性），也就是第2个、第3个和第4个点的值，然后将它们加起来。
换句话说，邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多，你的特征向量中心性就越高。
我们继续用矩阵A乘以结果向量。如何理解呢？实际上，我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散（点既给予也收获相邻节点）。我们猜测，这一过程最后会达到一个平衡，特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加，数值会越来越大，但我们最终会到达一个点，各个节点在整体中的比例会保持稳定。
现在把所有点的数值构成的向量用更一般的形式表示：
我们认为，图中的点存在一个数值集合，对于它，用矩阵A去乘不会改变向量各个数值的相对大小。也就是说，它的数值会变大，但乘以的是同一个因子。用数学符号表示就是：
满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。
特征向量中心性的计算需要读者具备矩阵乘法和特征向量的知识，但不影响这里读者对特征向量中心性思想的理解，不再赘述。
Betweenness centrality:中介中心性
如果一个节点位于很多条其他节点的最短路径上，那么改节点比较重要，定义如下：
我们可以看一个下面的例子：
假设我们要计算D的中介中心性：
- 首先，我们计算节点D之外，所有节点对之间的最短路径有多少条，这里是1条（在5个节点中选择两个节点即节点对的个数）。
- 然后，我们再看所有这些最短路径中有多少条经过节点D，例如节点A要想找到节点E，必须经过节点D。经过节点D的最短路径有3条（A-C-D-E，B-D-E，C-D-E）。
- 最后，我们用经过节点D的最短路径除以所有节点对的最短路径总数，这个比率就是节点D的中介中心性。节点D的中介中心性是3/1=3。
