我们回归下，如下图所示Graphs用来做传统机器学习任务的流程为：给定输入Graph,然后用来提取节点，边以及图级别的特征，之后学习模型（比如SVM,NN等等），最后将特征映射为标签。
1 引言
图表示学习可以减轻特征工程的需求，表示学习可以自动学习Graph的特征，用于下游任务，熟悉NLP的同学比较清楚，传统文本特征构建依赖于统计手段来实现，冗余且效果有限，在词向量Word2Vec和预训练模型Bert等出现之后，文本表示变得更为便利且效果强大，自此万物皆可Embedding。
图的表示学习的目的就是获得独立于不同任务的高效特征，通俗点讲就是能够针对不同任务学习得到适合任务的嵌入表示。
Node Embedding的目的就是能够将节点映射到不同的embedding空间：
- 节点间的embedding的相似性可以表示了节点间在网络的相似性：如果两个节点之间存在边，那么两个节点越相似
- 节点的Embedding能够编码网络信息
-
可以用于下游任务，比如节点分类，边的预测，图的分类等
下面是一个Zachary's Karate Club Network的2维节点Embedding展示：
2 节点嵌入：编码和解码
这一节我们主要掌握下如何学习节点的嵌入向量
2.1 构建输入-图
首先，假设我们有一个图：
-
代表节点的集合
-
代表链接矩阵
为了方便起见，我们默认认为节点没有其他的额外特征，如下图所示：
2.2 学习目标-Node Embedding
我们的目标是能够学习到节点的嵌入表示，这种节点嵌入的相似性能够近似节点在图中的相似性。
图中
2.3 学习方法-Encoder和Decoder
-
Encoder能够将节点映射成向量 - 定义一个节点相似性函数(比如节点在原始图中的相似性评估方法)
- Decoder
DEC能够将节点向量映射成相似性分数 - 优化编码器的参数：
原始网络的相似性：节点嵌入的相似性 ：
其中有两个非常关键因素：编码和相似性函数。编码器能够学习到节点的向量，相似性函数能够提供我们优化的目标，如果两个节点在图中存在边或者距离越近，那么它们对应的节点向量在向量空间中相似性也会越大。
如何选择定义节点相似性的方法是关键的地方，我们考虑下什么情况下，两个节点的相似性比较高？
- 是否存在边或者连接
- 是否共享邻居节点
- 是否包括相似的属性特征
接下来我们通过随机游走（Random Walks）来学习节点相似性，以及优化节点的嵌入向量。
3 Random Walk
Node Embeddings的计算方法之一就是Random Walk，为了方面起见我们定义和引出下面的符号，以便统一解释。
3.1 符号
为了方面接下来的公式推导，我们统一下符号标记：
- 向量
:
u节点的嵌入向量
- 概率
：
从节点
出发通过随机游走访问节点
的概率
- Softmax函数：通过softmax函数一作用，一个K维向量就映射成为(0,1)的值，而这些值的累和为1（满足概率的性质），那么我们就可以将它理解成概率，在最后选取输出结点的时候，我们就可以选取概率最大（也就是值对应最大的）结点，作为我们的预测目标。
- Sigmoid函数：
将一个数映射到（0,1）的区间
3.2 Random Walk 定义
给定一个Graph和一个起始点，我们选择随机选择该点的邻居节点，并且移动到该邻居节点；然后我们根据当前节点随机选择一个邻居节点，然后移动到该邻居节点，重复上述步骤...通过这种随机游走访问Graph节点的方式可以产生随机序列。下图描述了一个随机游走的实例，第一步从起始节点出发移动到节点5，第二步从节点5移动节点8，第三步从节点8移动节点9，第四步又从节点9移动到节点8，之后第5步移动到节点11，这样访问路径构成一个序列：
start_node->5->8->9->8->11
3.3 Random Walk如何得到Node Embeddings
相信大家对下面的公式不会感到陌生，一般我们衡量两个向量的相似性时可以通过两个向量点积计算得到，相似地两个节点同时出现在同一随机游走序列的概率可以用如下表示：
所以我们通过Rankdom Walk得到Node Embedding可以通过两个步骤：
(1) 通过某种随机游走策略
(2) 优化节点的embeddings表示，使得节点的嵌入表示能够表达或者近似我们上述随机游走得到的统计
回想一下我们机器学习或者深度学习的各种任务，无非就是在优化一个目标，一个近似目标，我们可以笼统地将我们输入表示成X，然后通过方法f来近似y。说到这里上面两个步骤特别像NLP中Glove向量的优化步骤，首先我们统计两个词在语料中共现概率，然后通过词向量来近似共现概率。
4.Biased Walks(->Node2Vec)
Node2Vec的核心思想是利用灵活的，有偏的随机采样序列。目的是在loca和global特征之间能够trade off。具体的做法是基于BFS和DFS。如下：
image
其中，BFS提供了关于neighbor的微观视角，DFS提供了关于neighbor的宏观视角。
image
截止现在，如何回答node similarity这个问题呢？
（1）如果两个节点是connected的，那么是相似的
（2）如果两个节点的neighbor是overlap的，那么是相似的
（3）基于Random Walk的方法
但是，没有一种方法适用于所有。Node2Vec在节点分类任务上表现更好，但是其他的方法在链接预测任务上表现良好，相似性的运用取决于自己的应用场景。但是无论怎样，基于Random Walk的方法的高效性，是真滴香。
启发：解决一个问题，刚开始用一个比较直白，朴素的方式来理解并尝试解决，之后逐步用并不显然，但是也能从一个方面反映问题本质的方法来求解，前提是这样的方法能够带来肉眼可见的提升。最后，要回过头来看，这种方法到底解决了啥子问题？
5.不能只有节点的表征，还要图的表征？
（1）对节点特征求和完事儿
（2）引用"virtual node"，代表subgraph，然后用得到节点表征的方式来做，本质上是考虑graph内生的层次性
（3）Anonymous Walk Embeddings（并没有深入研究）
6.怎么用这些Embedding？
7.知识表示
对于知识图谱中的一条边，可以用(h,r,t)来表示。其中，h和t表示实体，r表示关系。知识表示的目标是给定(h,r,t)，(h,r)的embedding和t的embedding是close的。这里的两个问题是：
（1）如何实现embedding？
（2）如何定义close？
这里的难点是关系模式的学习，典型的包括：对称关系，组合关系，1对N，N对1关系
这里的大框架定义的工作是从TransE开始的，后续各种TransX的工作，基本都没有脱离这种框架，同时Focus在各种复杂关系模式的学习上。
8 Random Walk 实现
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import random
# 创建图
G = nx.Graph()
# 添加节点
G.add_nodes_from(range(0,9))
# 添加边
G.add_edge(0, 1)
G.add_edge(1, 2)
G.add_edge(1, 6)
G.add_edge(6, 4)
G.add_edge(4, 3)
G.add_edge(4, 5)
G.add_edge(6, 7)
G.add_edge(7, 8)
G.add_edge(7, 9)
#画图
#nx.draw(G)
#plt.show()
# 添加遍历退出节点条件
red_vertices = [0, 2, 3, 9]
green_vertices = [5, 8]
# 成功命中次数
nsuccess = 0
# 随机游走次数
for step in range(1, 1000000):
# Choose a random start node
vertexid = 1
# 存储访问过的节点
visited_vertices = {}
# 存储路径
path = [vertexid]
print("Step: %d" % (step))
# Restart the cycle
counter = 0
# Execute the random walk with size 100,000 (100,000 steps)
for counter in range(1, 100000):
# Extract vertex neighbours vertex neighborhood
vertex_neighbors = [n for n in G.neighbors(vertexid)]
# Set probability of going to a neighbour is uniform
probability = []
probability = probability + [1./len(vertex_neighbors)] * len(vertex_neighbors)
# Choose a vertex from the vertex neighborhood to start the next random walk
vertexid = np.random.choice(vertex_neighbors, p=probability)
# Accumulate the amount of times each vertex is visited
if vertexid in visited_vertices:
visited_vertices[vertexid] += 1
else:
visited_vertices[vertexid] = 1
# Append to path
path.append(vertexid)
# If reached red break
if vertexid in red_vertices:
break;
# If reached green break
if vertexid in green_vertices:
nsuccess = nsuccess + 1
break;
# Organize the vertex list in most visited decrescent order
mostvisited = sorted(visited_vertices, key = visited_vertices.get,reverse = True)
print("Path: ", path)
# Separate the top 10 most visited vertex
print("Most visited nodes: ", mostvisited[:10])
print ("# of success: %d of %d" % (nsuccess, step))
print ("Probability of reaching green : %.12f" % (nsuccess / step))
网友评论