图表示学习（一）基于随机游走的方法

将关系数据构造成图（Graph）的形式有助于对复杂的关系和模式进行系统性的分析。社交网络、计算机网络、分子和生物网络、电网和交通网络等等现实场景都具有复杂图结构，在以往对图的研究一般集中于图论和拓扑学方法，近些年机器学习的发展将图与机器学习联系到了一起，图表示学习就是一种利用机器学习来提取图上节点特征的方法，在节点分类、社区挖掘、智能推荐领域有诸多应用。

机器学习任务的一般流程与概念

理解图表示学习在机器学习中的地位与用途，首先需要了解机器学习任务的整体概念，直接照搬书本上的各种形式化描述大概不会有太多人继续看下去吧，我们用一个最简单的图像分类模型训练任务来举个例子：

我们要解决一个简单的图像二分类问题：训练一个模型来区分出狗与人的图片，经典的机器学习应用有如下模式化的构建流程：

一个传统的图像分类模型训练流程

特征工程

在这个任务中，我们拥有两个已经标记好类别的图像集合（人、狗）用于训练，对于一张视觉上的二维图像（Image），在计算机内部的存储形式是一个2维（灰度图）或3维（RGB、CMYK等格式的彩色图）矩阵，然而，机器学习应用的数据源主要来自于以1维矩阵（向量）形式表示的数据。因此接下来就需要通过特征工程的方法将每张图像的数据矩阵数据转换为一个特定维度的向量，这个向量称之为特征向量。随后即可通过学习算法训练出模型，用于后续的各种图像识别、分类、切割等各种任务。

抽取某种特定成分的算法称之为特征算子。百度识图在约10年前刚推出的时候，以图搜图功能查询到的都是色调类似，但是内容完全不搭边的图片，据此可以推测百度当时使用的是色彩直方图作为特征算子抽取图像特征。色彩直方图描述了图像在每个色彩通道上像素明暗的统计特征，比如RGB格式图像就有红绿蓝3个色彩通道，色彩直方图统计了每个通道上明暗像素的数量比例，我们平时在Photoshop甚至相机上都可以看到图像的色彩直方图。

左边原图中存在一片橘红色与灰色区域，右图中去掉了灰色文字区域，对比左右两个色彩直方图可以看到左图三个通道的直方图中左侧的峰在右图中不存在，也意味着这三个峰值的存在可以表征左图中存在大片灰色区域。所以我们可以利用色彩直方图的这种特性来描述图像的明暗、总体色调等信息

色彩直方图只是一个特征工程中最浅显的例子，它只能够描述图像中的色彩统计信息，在实际应用中可以通过各种特征算子，如方向梯度直方图（Histograms of Oriented Gradients）、局部二值模式（Local Binary Patterns）等特征工程方法，提取出图像的色彩、结构、纹理等特征，将二维或三维图像转换为一个特征向量，并且能让这个特征向量蕴含图像的特定信息。

特征空间与分类面

在这个例子中，人和狗两个数据集在通过特征工程提取出特征向量后，每个样本（人或狗的图像）即可表示为一个高维空间中的一个点，这个点在这个高维空间中的坐标即特征向量的值，这个空间称为特征空间。

一般说来，一个良好的特征算子提取到的特征向量在特征空间中的位置具有如下特征：同类样本距离更近，非同类样本则具有较远的距离。

不同图像样本的特征向量在特征空间中的位置分布（实际场景中的特征向量维度远高于三维，通常为几百甚至更高维度），通常说来我们希望人的样本和狗的样本各自聚成一团，在样本间能有明确的界限。

在我们将图像映射到特征空间的点后，下一步的模型训练目的就是在特征空间中找到一个面将特征空间分为两部分，将大部分样本按照标定的类别分开，这个面称之为分类面。分类面根据采用模型算法的不同，可以是高维空间中的一个平面或曲面。

后续想要判断一张图片是人还是狗时，只需要使用同样的方法提取这张新图片的特征，并将其放入特征空间后观察它属于被划分出的哪个空间即可。

一个支持向量机（SVM）的分类面

介绍完机器学习任务的基本概念之后我们继续回到图的问题上，在图上进行机器学习的主要挑战之一是寻找一种方法可以将图或图上的部分结构表示为特征向量的方法，也就是上一节中提到的特征算子。上一节中的图像色彩直方图能够描述图像的色彩信息，在图上我们也需要一类特征算子能够将图的整体结构或图中每个节点附近的结构描述为一个特征向量。

传统的图特征算子比较依赖于用户定义的规则式方法以从图中提取能够编码图结构信息的特征，如节点度信息等。而图表示学习的目的是通过机器学习等手段将顶点、子图或整体图映射到向量空间中，然后对这些映射进行优化，使它们能够反映嵌入空间内的几何结构，然后所学习的嵌入可以用作机器学习任务的矢量输入，使得图数据可以应用到经典机器学习模型中。

将图中的节点的结构信息转换为向量信息

图表示学习的输出：每个节点都表示为一个特征向量

图表示学习的主要方法有以下几种：

1、基于随机游走的算法

2、基于矩阵分解的方法

3、图神经网络

4、图生成模型

在NLP（自然语言处理）中，word2vec是一种常用的词向量（word vector）计算方法，词向量可以很好地度量词与词之间的相似性。把 x 看做一个句子里的一个词语，y 是这个词语的一系列上下文词语，那么要训练的语言模型目的就是判断 (x,y) 这个样本是否符合自然语言的一般规则，更通俗点说就是：词语x和词语集合y是否经常在同一个语境里共同出现。

Word2vec 正是来源于这个思想，但它的最终目的不是训练语言模型，而是模型训练后的副产物：模型参数，并将这些参数，作为输入 x 的某种向量化的表示，这个向量便叫做词向量。

deepwalk是第一个被提出来使用表示学习（或深度学习）社区的技术的网络嵌入方法。这种方法利用了上述NLP中词向量的原理，利用图中节点与节点之间的近邻共现关系来学习节点的向量表示。那么关键的问题就是如何将图的结构转换为语句的结构，在deepWalk中提出了利用随机游走 (RandomWalk)的方式在图中进行节点采样。将图中复杂的顶点间关系转换为顶点序列，用于模拟NLP语料库中的每个句子。

随机游走是一种深度优先遍历算法，与常规的深度优先遍历算法的差异是它可以重复访问已经访问过的节点：给定当前访问起始节点，从其邻居中随机选取一个节点作为下一个访问节点，并一直重复此过程，直到最终得到的访问序列长度满足用户指定序列长度。

deepwalk的具体实现分为两个步骤：

1、采用在图上进行随机游走的方式采样

2、使用word2vec方法对采样得到的节点序列计算图嵌入向量

采用python实现的deepwalk随机游走采样代码如下：

def deepwalk_walk(self, walk_length, start_node):
     walk = [start_node]
     while len(walk) < walk_length:
        cur = walk[-1]
        cur_nbrs = list(self.G.neighbors(cur))
        if len(cur_nbrs) > 0:
            walk.append(random.choice(cur_nbrs))
        else:
            break
    return walk

对于上一步得到的采样序列，在word2vec中需要通过滑动窗口的方式将其上下文限定在一个相对较小的范围，如[4,3,1,5,1]这样一个访问序列，用尺寸为3的滑动窗口可以得到[4,3,1][3,1,5][1,5,1]三个训练样本。再将训练样本放到机器学习模型中训练以为每个顶点得到一个合适的向量表示。

通过对一系列输入样本的训练，将一个顶点vj映射为一个d维向量Φj

对多次重复采用得到的样本集进行word2vec计算，获得节点向量

from gensim.models import Word2Vec
w2v_model = Word2Vec(walks,sg=1,hs=1)

node2vec是deepWalk的一种扩展，它引入了一个有偏的随机游走策略用于结合广度优先和深度优先两种图遍历策略的特点。

BFS（Breadth First Search）广度优先遍历，DFS（Depth First Search）：深度优先遍历

node2vec通过两个参数来进行有偏的随机游走：p和q，p控制访问已经访问过的节点概率，q控制访问新节点概率

通过参数p和q控制随机游走偏向于DFS还是BFS

struc2vec考虑的重点是图节点附近结构的相似性问题，上图的这个网络中，尽管节点u与v在网络结构上很相似，但是因为其距离较远，因此如deepwalk和node2vec等直接在图上进行随机游走的算法很难将这两个节点作为上下文节点进行训练，在生成的嵌入向量上其差距也会比较大。struct2vec通过节点邻居的度信息构造一个多层次的网络来提高这类结构相似节点之间的权重，最终在随机游走采样时这些结构相似节点就很可能被采样到同一个上下文中。

首先，struc2vec会分别统计每个节点的k度距离邻居，以及每个邻居的度数，以每个节点外扩k层的每个邻居度数统计信息来表征这个节点的网络结构形态：

取每个节点的k层距离顶点统计特征

随后，根据上一步获得的每个顶点k层统计信息，构造一个多层带权图（multilayer weighted graph），每个层次中的节点u，v的距离均通过以下距离函数计算得到，

通过距离函数，可以为图上任意两个顶点添加一条直连边，边的距离即节点间的结构相似程度，越相似距离越近。同时在同一个顶点的多层之间也添加了边，使得最终随机游走时能够到达相邻层次节点。

struc2vec算法构建的多层带权图，其中包含两种边：一、跨层次的边，用于连接不同层次的同一个顶点；二、同层次的边，用于记录与其它节点的距离并进行随机游走

 构建完多层带权图后，即可根据不同节点间的距离以及不同层次节点间的权重进行随机游走，获取节点采样序列：

随机游走的采样过程可以在同一层次内，也可以在跨越层次进行

当我们通过某种方法获得了图中每个节点的嵌入表示时，想知道这种方法获得的嵌入表示是否具有良好的可分性（同类间间隔小，类别之间间隔大），除了通过交叉校验的方式将特征分为训练与验证集训练机器学习模型以评判其可分性。同时也可以通过降维算法将图嵌入表示的特征向量从高维降低到人眼可观察的2或3维。如果在低维空间中这些样本是可分的，那么他们在原始的高维空间中也一定可分，如果低维空间中不可分，那么可能是这种嵌入算法并不合适，也有可能是他们在高维可分低维不可分而已。

在传统上，把数据从高维降到低维一般会使用PCA方法，在2008年提出的t-SNE方法具有比以往降维方法更好的效果。

下面举个例子解释下利用这种降维方法在2维空间中展示特征向量是否具有可分性:

我们有一个手写数字的图像集，其中每个图像的大小为8x8像素，我们直接将这个8x8的矩阵逐行拼接为一个64维向量作为图像的特征向量，随后采用t-SNE算法将特征向量从64维降到2维，最后就可以将整个数据集的坐标在平面上绘制出来：

from time import time
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.manifold import TSNE


def plot_embedding(data, label, title):
    x_min, x_max = np.min(data, 0), np.max(data, 0)
    data = (data - x_min)  (x_max - x_min)
    fig = plt.figure()
    for i in range(data.shape[0]):
        plt.text(data[i, 0], data[i, 1], str(label[i]), color=plt.cm.Set1(label[i]  10.))
    return fig


digits = datasets.load_digits(n_class=6)
data = digits.data
label = digits.target
tsne = TSNE(n_components=2, init='pca', random_state=0)
result = tsne.fit_transform(data)
fig = plot_embedding(result, label, '')
fig.show()

每个图像特征降到二维后的空间位置

节点分类能力

struc2vec的作者在论文的实验部分贴出了这张与node2vec的对比结果，可以看到相对于node2vec的精确度，struc2vec及其各种近似优化算法（OPT1/2）的效果均提高了10%-20%

基于论文中的flight数据集，使用开源的deepwalk/node2vec/struc2vec算法实现进行对比：

Flight数据集，包含了机场与航班的关系，并人工按照机场繁忙情况标注为四类

采用3种图嵌入算法分别提取的节点特征，降到2维之后的分类情况，可以看出struc2vec算法在各个类内的聚集程度上相对其它算法更好，在类与类之间具有相对较大的间隔。

deepwalk的节点混淆最严重；node2vec节点也存在混淆，看不出明确的分类面；struc2vec除了红色和部分绿色类别节点外，其它类别基本上能做到相对良好的分类

社区挖掘能力

在这里使用的是wiki上的条目引用网络关系数据，用来对wiki条目的社区分类情况进行挖掘，图中共有2405个节点和月1.8万条边。

图中可以看到，deepwalk和node2vec约有一半的类别能够聚合在一起，社区挖掘能力不相上下，struc2vec因为采样时更多地考虑了结构相似性，对近邻节点的采样力度较小，因此虽然节点聚合得很紧密，但是每个群落中都混杂了各个不同社区的节点。因此对于社区检测任务，deepwalk和node2vec的效果更好

资源消耗对比

从算法上可以看出，deepwalk和node2vec直接在图上进行随机游走以采样，算法简单速度快，其CPU与内存资源消耗均较小，而struc2vec需要构建多层带权图，需要更多的内存与计算时间。在一台笔记本上，前两个算法处理几万个节点的数据只需要几秒，而struc2vec需要十几分钟以及上G的内存。因此在面对大数据集而言，struc2vec还需要根据实际场景配合各种优化策略一起使用。

参考文献

[1] Bryan Perozzi, Rami Al-Rfou, Steven Skiena. 2014. DeepWalk: Online Learning of Social Representations. KDD

[2] Aditya Grover, Jure Leskovec. node2vec: Scalable Feature Learning for Networks

[3] Leonardo F. R. Ribeiro, Pedro H. P. Savarese, Daniel R. Figueiredo. 2017. struc2vec: Learning Node Representations from Structural Identity

[4] FENXIAO CHEN, YUNCHENG WANG, BIN WANG AND C.-C. JAY KUO. Graph Representation Learning: A Survey

[5] William L. Hamilton and Jian Tang. Graph Representation Learning. AAAI2019