第三篇：图

发表信息: by Creative Commons Licence

目录

正文

图由节点和边组成

一个节点可能与众多节点直接相连，这些节点被称为邻居

图算法

是一种用于图数据的查找算法

用于解决两类问题

第一类：从节点A出发，有前往节点B的路径吗

第二类：从节点A出发，前往节点B的哪条路径最短

如何实现呢？

比如在上述A,B,C,D,E 构成的关系图中，想看A,E是否存在相通的道路，A,E如果相通，最短的路径是哪条。

让我们一度、二度依次来看（什么是一度、二度呢？我的朋友是一度，朋友的朋友是二度）

A的一度朋友有B,C，添加到列单里 ==> {B,C}, B,C中都没有E, 因此接着看二度

B的一度朋友有D，添加到列表里 ==> {B,C,D}

C的一度朋友有B,D，添加到列表里 ==> {B,C,D}

D的一度朋友有E， bingo

要用代码实现上述过程，首先应获取所有的关系数据，这种对应关系，散列表可以实现

|--------+--------|
|        |   B    |
|    A   |--------|
|        |   C    |
|--------+--------|

graph = {}
graph['A']=['B','C']
graph['B']=['D']
graph['C']=['B','D']
graph['D']=['E']
graph['E']=[]

实现：通过构建一个搜索队列

代码实现：

首先创建一个队列，python中可使用deque创建了一个双端队列

from collections import deque
search_queue = deque()
search_queue += graph["A"]  # 将A的邻居都加入到这个搜索队列中

完善这个算法代码

while search_queue:                    # 只要队列不为空
	node = search_queue.popleft()      # 就取出其中的第一个人
	if node_is_E(node):                # 检查节点是否为E
		print("node %s is E")%node
		return True
	else:
		search_queue += graph(person)  # 不是节点E，将这个节点的邻居都加入搜索队列中

继续补充

def node_is_E(name):
	return name == 'E'

接下来看广义优先搜索的执行过程：

上面可以看到，检查了D两次，其实是没有意义的。因此应该将其标记为已检查。

从而完整的BFS代码为

def search(name):
	search_queue = deque()
	search_queue += graph[name]
	searched = []
	while search_queue:
		node = search_queue.popleft()
		if node not in searched:
			if node_is_E(node):
				print('bingo')
				return True
			else:
				search_queue += graph[node]
				searched.append(node)
	return False

运行时间：O(V+E)

上面这个例子意味着A将沿每条边前行，因此运行时间至少为O(边数)。

还使用了一个队列，其中包含要检查的每个节点。将一个节点添加到队列需要的时间是固定的，即O(1)。因此对每个节点都这样做，需要的总时间是O(节点数)

所以广度优先搜索的运行时间为O(边数+节点数），通常写作O(V+E)

其他不错的例子：

拓扑排序：

根据图创新的列表是有序的。如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称之为拓扑排序

使用它可根据图创建一个有序列表。

假设你正在规划一场婚礼，并有一个很大的图，其中充斥着需要做的事情，但却不知道要从哪里开始。这时就可以使用拓扑排序来创建一个有序的任务列表。

还有一个例子是家谱，家谱图只有向下没有向上的箭头，这种图又称之为树。

广度优先搜索指出是否有从A到B的路径，如果有，广度优先搜索将找出最短路径。

Deepwalk

利用构造节点在网络上的随机游走，来模仿文本生成的过程，提供一个节点序列。

然后用skip-gram和Hierarchical softmax模型，对随机游走序列的每个局部窗口内的节点进行概率建模。

最大化随机游走序列的似然概率，并使用最终随机梯度下降学习参数，进而产生图的节点的嵌入表示。

一般是针对图中的每个节点v属于V，产生N个长度为l的随机游走序列，然后用合适的窗口w去采样抽取其中的节点特征。

Deepwalk选取随机游走序列中的下一个节点的方式是均匀随机分布的。

假设一个相连图（connected graph）的度分布（degree distribution）服从power law分布（比如scale-free），那么可以观察到节点在短随机游走过程中出现的频率也会服从power-law分布。

Language Model：

目标是估计【语料库中出现特定词组序列的似然函数】。

即：

近期工作集中于使用概率神经网络（probabilistic）去建立节点表示，远远超过上述想要达到的目标

目标是学习潜在的表示，而不仅仅是节点之间同时出现的概率分布。所以引入一个映射函数。然后问题就转换为：

然而随着游走长度的增加，计算这个条件概率就变成很难。

最近有一些变化，首先，不再用文本去一个单词，而是用单词去预测文本；其次，由单词构成的文本同时出现在给定单词的左侧和右侧；最后，移除了顺序限制。

因此要求模型最大化任何一个单词出现在文本中的概率(without the knowledge of its offset from the given word)，

这些变化是有利于社区表达学习的。首先，顺序独立，可以更好的捕捉由随机游走带来的“邻近”；其次，可以很好的缩减训练时间。

最优化上面的公式，建立了代表，能够捕捉两个节点之间的局部图结构。节点有相似的邻居，就会有相似的表达。

通过结合【截断随机游走】和【语言模型】，可以获得满足所有理想性质的方法。

node2vec

与deepwalk不同，n2v选取随机游走序列中下一个节点的方式不是均匀随机分布，而是引入两个参数p和q

将宽度优先搜索和深度优先搜索引入随机游走序列的生成过程。

宽度有限搜索（BFS）注重临近的节点，并刻画了相对局部的一种网络表示 p 局部微观结构

深度优先搜索（DFS）反应了更高层面上的节点间的同质性。 q 全局宏观结构 BFS能够探究图中的结构性质，DFS能够探究出内容上的相似性（相邻节点之间的相似性）

直观上，p和q控制了探索和离开起始节点u的领域的速度。

其中结构相似性不一定要相连接，甚至可能相距很远。

如上图所示：t是v的上一个节点，x1，x2，x3是v的下一个节点。

那么返回上一个节点t的概率是1/p，

x1离t的距离和v离t的距离相同，因此进入节点x1的概率是1

x2和x3是v的下一个节点，进入的概率是1/q

n2v根据p和q定义了不同的邻居的跳转概率，p控制着跳向上一个节点的邻居的概率，q控制着跳向上一个节点的非邻居的概率

即，p是控制访问走过的node，即往回走；q是控制访问还没有走过的node，即向外走。

写成公式即：

n2v通过半监督形式，利用网络搜索最适合的参数学习节点表示。

特别是，在网络节点上的预测任务往往在两种相似点之间穿梭：同质性和结构等价性。

在同质性假设下：高度互联且属于相似网络集群或社区的节点应紧密嵌入在一起（例如上图的节点s1和u属于同一网络社区）

在结构等价性的假设下，在网络中具有相似结构作用的节点应该紧密地嵌入在一起（例如上图中的节点u和s6作为其相应社区的枢纽）

与同质性不同，结构等价性不强调连通性；节点可以在网络中相隔很远，并且仍然具有相同的结构角色。

在现实世界中，这些等价概念并不是唯一的； 网络通常表现出两种行为，其中一些节点表现出同质性，而另一些反映出结构等价性。

BFS和DFS策略在生成【反映上述任意一种等价的表示方面】起着关键作用。

BFS取样的社区导致了与结构等效性紧密对应的嵌入。（为了确定结构上的等价性，准确地描述局部社区通常就足够了）

例如基于网络角色的结构等价可以通过观察每个节点的近邻来推断。 BFS通过将搜索限制在附近的节点上，实现了这种特性，并获取了每个节点领域的微观视图。

此外，在BFS中，抽样领域中的节点往往重复多次。减少了描述1-hop节点相对于源节点的分布的方差。

DFS可以探索网络的更大部分，因为可以远离源节点u（样本容量为k）。

采样节点更准确的反映了邻域的宏观视图。这在基于同质性的社区推断中是必不可少的。 DFS不仅要推断网络中存在哪些节点到节点的依赖关系，还要确定这些依赖关系的确切性质。 这一点很难，因为有一个约束的样本大小和一个要探索的大的邻居，导致高方差。

其次，移动到更大的深度会导致复杂的依赖关系，因为采样节点可能离源很远，而且可能不具有代表性。

BFS和DFS是分别适应于结构等效性和同质性的极端抽样范式。

但在现实中，这些等效性的概念并不是互相竞争或者互相排斥的，现实网络通常是两者的混合体。

因此可以设计一个灵活的领域采样策略，使我们能够在BFS和DFS之间平滑差值。通过开发一种灵活的偏差随机游走。

上面说的意思就是：

最简单的有偏随机游走，就是根据边的权重w。但是仅仅根据边的权重不足以考虑网络结构，不足知道探索不同类型的网络邻居。

这样做的空间复杂度

相关采样算法

随机点采样(Random Node)

随机边采样(Random Edge)

广度优先算法(Breadth First Search)

随机游走采样(Random Walk)

Metropolis-Hasting 随机游走采样(MH Random Walk)

双网络图采样(Bi-graph Random Walk)

skip-gram 模型

skip-gram模型实际上分成了两个部分：

第一部分：建立模型

第二部分：通过模型获取嵌入词向量

和自编码器(auto-encoder)思想很像

即，先基于训练数据构建一个神经网络。当这个模型训练好了以后，并不需要使用这个模型。需要的是这个模型训练数据所得的参数。例如隐藏层的权重矩阵。

这个过程又称为“Fake Task”

补充：

auto-encoder

无监督特征学习(unsupervised feature learning)

通过在隐藏层将输入进行编码压缩，继而在输出层将数据解码恢复初始状态

在训练完成后，将输出层“砍掉”，仅保留隐藏层。

训练神经网络过程:

首先由一个节点序列，如[a,b,c,d,e,f,h]，选择其中的一个节点作为输入，如[c]作为input node

定义参数：skip_window，代表从当前input node的一侧（左边或右边）选取节点的数量。如果设置skip_window=2，那么最终获得窗口中的节点是[a,b,c,d,e]

定义参数：num_skips，代表从整个窗口中选取多少个不同的词作为output node。

当skip_window=2, num_skips=2时，会得到两组(input node, output node)形式的训练数据。即(c,a),(c,b),(c,d),(c,e)

神经网络基于这些训练数据将会输出一个概率分布，这个概率代表我们节点库中的每个节点是output node的可能性。

具体来说，以(c,d)这组数据来训练神经网络，那么模型通过学习这个样本，会告诉我们节点库中每个节点是[d]的概率大小。 模型的输出概率代表着我们节点库中每个节点有多大可能性跟input node同时出现。

通过给神经网络输入图中成对的节点来训练完成概率计算。

具体过程如下：

我的疑问：像离的远的节点，不应该有个类似的衰减系数吗？

模型细节：

如何表示这些单词呢？

神经网络只接受数值输入

最常用的方法是基于图来构建自己的节点库，再对节点进行one-hot编码。

像上文的是七个不重复的节点，就可以映射成7维向量，输入是7维向量，输出也是7维向量。输出的7维向量，包含了7个概率。

下图是神经网络的结构：

隐层没有使用任何激活函数，但是输出层使用了softmax。

隐藏层：

如果现在想用4个特征来表示一个节点，那么隐藏层的权重矩阵应该是7*4，隐藏层有4个节点。也就是把节点的7维变成4维。

所以我们最终的目的就是学习这个隐藏层的权重矩阵。

注意：

input node 和 output node 都会被进行one-hot编码。这样的向量相当系数，会消耗大量的计算资源。

为了高效的计算，这个模型仅仅会选择矩阵中对应的向量中维度值为1的索引行。如下图：

为了有效的进行计算，这种稀疏状态下不会进行矩阵乘法计算。

可以看到，矩阵的计算实际上是矩阵对应的向量中值为1的索引。

上面的例子中，左边向量中取值为1的对应维度为3，那么计算结果就是矩阵的第3行。 这样模型中的隐层权重矩阵变成了一个“查找表”（lookup table） 在进行矩阵计算时，直接去查输入向量中取值为1的维度下对应的那些权重值。

隐藏层的输出就是每个输入单词的“嵌入词向量”

输出层：

经过神经网络隐藏层的计算，节点会从1×7的向量变成1×4的向量，再被输入到输出层

输出层是一个softmax回归分类器，它的每个节点将会输出一个0-1之间的值（概率），这些所有输出层神经元节点的概率之和为1

下面是一个例子：

直觉上的理解：

如果两个不同的节点有着非常相似的“上下文”（也就是窗口节点很相似，比如“aa b c d”，“ee b c d”。通过模型的训练，这两个单词的嵌入向量将非常相似。

从前面可以看到skip-gram是一个超级大的神经网络（权重矩阵规模非常大）

比如我们拥有一个10000个节点的节点库，想嵌入300维的节点向量，那么输入-隐藏层权重矩阵和隐藏层-输出层的权重矩阵都会有10000×300=300万个权重

在如此庞大的神经网络中进行梯度下降是相当慢的。

更糟糕的是，你需要大量的训练数据来调整这些权重并且避免过拟合

百万数量级的权重矩阵和亿万数量级的训练样本，意味着训练这个模型将会是个灾难。

为了解决这些问题，可以采取：

对常见的节点组合(node pairs)或者路径作为单个"nodes"来处理

对高频次节点进行抽样来减少训练样本的个数

对优化目标采用"negative sampling"方法，这样每个训练样本的训练只会更新一小部分的模型权重，从而降低计算负担。

事实证明，对常用节点抽样并对优化目标采用"negative sampling"方法，不仅降低了训练过程中的计算负担，还提高了训练的质量。

对高频次抽样，以文本处理为例：

抽样率：

还有一个参数：sample，代表阈值，默认是0.001。这个值越小意味着这个单词被保留下来的概率越小（即有越大的概率被我们删除）

负采样（negative sampling）

训练一个神经网络意味这样要输入训练样本并且不断调整神经元的权重，从而不断提高对目标的准确预测。每当神经网络经过一个训练样本的训练，它的权重就会进行一次调整。

不同于原本每个训练样本更新所有的权重，负采样每次让一个训练样本仅仅更新一小部分的权重，这样就会降低梯度下降过程中的计算量。

在用训练样本(input node:a, output node:b)来训练神经网络时，a和b都是经过one-hot编码的。如果节点库的大小为10000时，在输出层，期望对应b节点的那个神经元节点输出1，其余9999个都应该输出0

这里，这9999个期望输出为0的神经元结构所对应的节点成为“negative node”

当使用负采样时，将随机选择一小部分的negative nodes（比如5个），来更新对应的权重，也会对positive nodes进行权重更新，即b。

在论文中，作者指出对于小规模数据集，选择5-20个negative nodes会比较好，对于大规模数据集可以仅选择2-5个negative nodes 假设隐藏层-输出层拥有300×10000的权重矩阵，如果使用了负采样的方法，仅仅去更新positive node-“b”和选择的其他5个negative nodes的结点对应的权重，共计6个输出神经元，相当于每次只更新300×6=1800个权重

对于300万的权重来说，相当于只计算了0.06%的权重，这样计算效率就大幅度提高。

如何选择negative nodes

选择“一元模型分布（unigram distribution）

一个节点被选作negative sample的概率跟他出现的频次有关，出现频次越高的节点越容易被选作negative nodes。

三、狄克斯特拉算法

找出加权图中前往X的最短路径

前面是根据图中边的个数去判断路径长短，如果边是有权重的呢？（也就是广度优先搜索，找出的是段数最少的路径，如果要找出最快的路径呢）

例如在汽车行驶过程中，两点之间的时间长短会受到距离长短和拥堵程度影响，因此不同点之间应该有相应的权重赋值。

例如下图的区别：

狄克斯特拉找到的是总权重最小的路径。

狄克斯特拉算法包含4个步骤：

以下图为例：

1、找出“最便宜”的节点，即可在最短时间内到达的节点

站在七点，不知道应该往节点A还是往节点B。假设前往节点A要6分钟，前往B要2分钟。由于不知道前往终点需要多长时间，因此假设为无穷大。从这个角度考虑，节点B最近，选择节点B

2、更新该节点的邻居开销

从节点B出发，计算经节点B前往其各个邻居所需的时间。发现！经B节点，前往A节点，需要5分钟，而直接前往A节点需要6分钟！

对于节点B的邻居，如果找到前往它的最短路径，就更新其开销： 在这里发现：

~ 前往节点A的更短路径（时间从6分钟缩短到5分钟）

~ 前往终点的更短路径（时间从无穷大缩短到7分钟）

3、重复这个过程，直到对图中的每个节点都这样做了

重复第一步：终点最短时间内前往的节点。前面已经对节点B执行了第二步，除节点B外，可在最短时间内前往的节点是节点A

重复第二步：更新节点A的所有邻居开销。发现前往终点的时间为6分钟。？？？

到目前为止，已经知道：

前往节点B需要2分钟

前往节点A需要5分钟

前往终点需要6分钟

4、计算最终路径

其他：

狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重。

带权重的图称为加权图。不带权重的图称为非加权图。

图还有环，如下图：

有环就意味着，可以从一个节点出发，走一圈后又回到这个节点，

绕环前行是否合理呢？你可以选择避开环的路径，也可以选择包含环的路径。

这两条路径都可以到达终点，但环增加了权重，如果愿意，可绕环两次。但每绕环一次，总权重都增加8。因此，绕环的路径不可能是最短的路径

无向图意味着两个节点彼此指向对方，其实就是环。

在无向图中，每一条边都是一个环，迪克斯拉特算法只适用于有向无环图（directed acyclic graph, DAG）

《算法图解》中换钢琴的例子，第101页。感觉上面四个步骤，写成列表更清楚

上面知道最短路径的开销是35美元，但是如何确定这条路径呢？

首先找出钢琴的父节点：是架子鼓，架子鼓的父节点是唱片，唱片的父节点是乐谱。

由此，可以知道完整的交换路径是：乐谱 ==> 唱片 ==> 架子鼓 ==> 钢琴

负权边

有可能存在下面这种情况：

也就是边的权重是负的！

如果有负权边，就不能使用狄克斯特拉算法。原因见《算法图解》107页

因为狄克斯特拉算法的一个假设是：对于处理过的海报节点，没有前往该节点的更短路径。这一点也体现出为什么一个一个选最便宜的节点，这样的顺序重要性。

代码实现：

以下图为例：

解决上图这个问题，需要三个散列表。随着算法的进行，将不断更新散列表【开销表】和【父节点表】。

先将上面的图关系存进散列表中去（散列表中又包含散列表）

graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

接下来建立一个散列表存储每个节点的开销

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

还需要一个存储父节点的散列表

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

最后，需要一个数组，用于记录处理过的节点。

因为对于同一个节点，不用处理多次。

processed = []

算法过程如下：

代码如下：

node = find_lowest_cost_node(costs)  # 在未处理的节点中找出开销最小的节点
while node is not None:			     # 这个while循环在所有节点都被处理后结束
	cost = costs[node]
	neighbors = graph[node]
	for n in neighbors.keys():  #遍历当前节点的所有邻居
		new_cost = cost + neighbors[n]
		if costs[n] = new_cost:
			cost[n] = new_cost
			parents[n] = node
	processed.append(node)
	node = find_lowest_cost_node(costs)

随机游走 random walk

一般提及的随机游走是指DeepWalk中的随机游走，选择下一步节点是随机的。

除此之外还有node2vec中的2nd order随机游走。随机游走下一步的选择不是均匀的随机的，而是有偏的。

在node embedding里，有很多encode的方法，比如“shallow” encoding，Adjacency, Multi-hop, random walk.

其中需要理解的概念有：negative sampling。

如何进行随机游走呢？

最简单的方法有：固定长度，无偏的随机游走，从每个节点开始。

还可以，使用灵活的，有偏的随机游走，从局部和全局角度来划分，可以分成BFS和DFS，也是前面所说的广度优先算法和深度优先算法。node2vec

其他随机游走的方法还有：

不同类型的有偏随机游走：基于节点性质的，基于学习到的权重的。 其他优化方法：基于一跳二跳随机游走概率的优化 网络处理技术：基于修正后的网格进行随机游走。

随机游走的公式：

随机游走的优点：

1，只依赖于局部信息，所以可适用于分布式和在线系统，而使用邻接矩阵就必须把所有信息存储于内存中处理，面临着较高的计算时间和空间消耗

2，对随机游走序列进行建模可以降低建模0-1二值邻接矩阵的方差和不确定性

随机游走矩阵可以看做是马尔科夫链的一种特例。

对于一个图G的邻接矩阵A来说，A中的非零元素描述了图G中每一条边的权重（这里一般要求A的对角线为0）。 这个权重描述了节点之间的相似性。如果我们对A进行按行归一化，即

D是A的度矩阵，是一个对角阵，对角线元素。这样得到的矩阵P就是一个随机游走矩阵。每个点与其他所有节点的跳转概率之和为1。

一个随机游走矩阵对应的是一个遍历的马尔科夫链，也就是说任意两个状态之间都可以互相到达。经过一步转移，下一时刻的概率为：

这样一直进行下去，经过一定时间可以到达稳态。所谓稳态，就是说状态的概率分布不再进行变化。 上述方程已经说明：稳态实际上就是随机游走矩阵，特征值1所对应的特征向量。另一种计算稳态的方法是：

马尔科夫链的基础矩阵定义为：

其中I是一个单位阵，P为对应的随机游走矩阵，W是将稳态按行堆叠形成的矩阵。

对于一个正规的马尔科夫链（即P的任何次方都没有负值的元素），W可以看做n趋于无穷大的情况。 通过基础矩阵，可以计算马尔科夫链的很多特性，其中主要包括了各种访问时间：

从状态i出发返回状态i的时间期望

从状态i出发，回到状态i之前，访问状态j的次数期望

从状态i出发，到达状态j的时间期望。

从状态j出发，到达状态j之前，访问状态j的次数期望

从稳态出发，到达状态i的时间期望

从稳态出发，到达状态i之前，访问状态j的次数。

对应有三个定理：

对状态i

对状态j

对任意状态i

[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)