作者:太子長琴(NLP算法工程师)
Paper:node2vec: Scalable Feature Learning for Networks
Code:aditya-grover/node2vec
核心思想:通过给网络节点的邻居定义一个灵活的概念,并设计了一个能够有效探索邻居多样性的有偏随机游走程序,来学习网络的节点表征。
许多任务涉及图节点和边的分析。
G = (V, E)
f → R, size |V | × d 表示节点特征表征向量
Ns(u) ⊂ V 表示采样策略 S 下节点 u 的邻居
相关假设:
条件独立:
对称性:源节点和邻居节点在特征空间中彼此对称。
最后的损失函数:
其中,
BFS 和 DFS
网络中节点上的预测任务经常在两种相似性之间交织:同构和结构对等。
通过 BFS 采样的邻域会导致与结构对等紧密对应的嵌入。在 DFS 中,采样的节点更准确地反映了邻域的宏观视图,这对于基于同构性推断社区至关重要。
这里稍微解释下,根据 BFS 采样,意味着只要节点邻域类似,节点就类似,这个距离可能很远,其结果就是结构对等的相似;根据 DFS 采样,意味着节点可能比较接近,属于同一社区,其结果就是同构相似。
node2vec
node2vec 通过一种灵活的偏向随机游走程序来抽样,可以同时以 BFS 和 DFS 方式探索邻域。
给定起始节点 u,ci 是随机游走的第 i 个节点,所以 c0 = u:
π_vx 是 v 和 x 之间未归一化的转移概率,Z 是归一化常数。假设刚从 t 节点转移到 v 节点:
d 表示节点间的最短距离,必须是 0 1 或 2。直觉上看,p 和 q 控制程序多快探索或离开 u 的邻居节点,具体的,允许程序近似地在 BFS 和 DFS之间插值。
Algorithm
# 对所有节点执行 num_walks 轮随机游走
def simulate_walks(num_walks, walk_length):
walks = []
nodes = list(G.nodes())
for walk_iter in range(num_walks):
random.shuffle(nodes)
for node in nodes:
walks.append(node2vec_walk(walk_length=walk_length, start_node=node))
return walks
# 节点随机游走(本文核心代码)
def node2vec_walk(walk_length, start_node):
walk = [start_node]
while len(walk) < walk_length:
cur = walk[-1]
cur_nbrs = sorted(G.neighbors(cur))
if len(cur_nbrs) > 0:
if len(walk) == 1:
nxt = cur_nbrs[alias_draw(alias_nodes[cur][0],
alias_nodes[cur][1])]
else:
prev = walk[-2]
nxt = cur_nbrs[alias_draw(alias_edges[(prev, cur)][0],
alias_edges[(prev, cur)][1])]
walk.append(nxt)
else:
break
return walk
随机游走得到的是节点序列,每个序列的长度为 walk_length
,共有 num_walks * num_nodes
个序列。所有的序列丢入 Word2Vec 模型训练即可得到 node 向量。
alias_draw
的实现比较简单:
def alias_draw(J, q):
K = len(J)
kk = int(np.floor(np.random.rand()*K))
if np.random.rand() < q[kk]:
return kk
else:
return J[kk]
可以看出其主要作用就是随机从 J 中取出一个元素。
重点是 alias_nodes
和 alias_edges
,二者分别遍历所有节点和边,为每个节点和边生成 alias。
def get_alias_node(node):
unnormalized_probs = [G[node][nbr]['weight'] for nbr in sorted(G.neighbors(node))]
norm_const = sum(unnormalized_probs)
normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
return alias_setup(normalized_probs)
def get_alias_edge(src, dst, p, q):
'''
src: t
dst: v
dst_nbr: x
'''
unnormalized_probs = []
for dst_nbr in sorted(G.neighbors(dst)):
w_vx = G[dst][dst_nbr]['weight']
if dst_nbr == src:
unnormalized_probs.append(w_vx/p)
elif G.has_edge(dst_nbr, src):
unnormalized_probs.append(w_vx)
else:
unnormalized_probs.append(w_vx/q)
norm_const = sum(unnormalized_probs)
normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
return alias_setup(normalized_probs)
节点直接使用了权重(毋庸置疑)作为转移概率,边使用了上面的公式计算转移概率。关于 alias_setup
放在了最后面的 “附录” 部分,可以移步查看。
Edge Features
就是根据不同的操作方式定义了几种 “边” 的定义,label 就是边是否存在。
主要贡献在于定义了节点网络邻居的一个灵活概念。通过有偏差的可以有效探索给定节点不同邻域的随机游走族来实现。
提出了 node2vec,一种网络特征学习的高效可伸缩算法,它使用 SGD 有效地优化了一种新颖的网络感知的邻域保留目标。
展示了 node2vec 如何符合网络科学中的既定原则,为发现符合不同等价关系的表示形式提供了灵活性。
将基于邻域保留目标的 node2vec 和其他特征学习方法从节点扩展到成对的基于边缘的预测任务的节点对。
根据经验评估 node2vec 的多标签分类和对几个实际数据集的 link 预测。
首先需要通过节点和关系来构造图,输入很简单:n 行,每行分别是起始节点、终止节点、权重,输入数据默认是有向的。
G = nx.read_edgelist('data.edgelist', nodetype=int,
data=(('weight', float),), create_using=nx.DiGraph()) # 有向图
G = G.to_undirected()
这样就完成了图的构建。
输入构造完后首先需要预处理,然后随机游走,最后利用 Word2Vec 进行训练。
(num_walks * num_nodes) × walk_length
。num_nodes × dimensions
。训练完后得到的其实就是一个 Word2Vec 的模型,使用方法并无差别。
数据处理和模型都不复杂,看看实验参数情况。
Multi-label classification
这里主要和三种方法做了对比:
这个 Gain of node2vec 意思是采用 pq 设置带来的增益。
这里的 x 轴表示训练-测试数据比例。
参数敏感性
低 q 倾向于向外探索,低 p 倾向于在节点附近。d 包括 r, l, k。k 就是训练词向量时的窗口大小。最后一列的两幅图分别表示缺失边和随机边。
Link prediction
随机移除 50% 的边作为正例,负例随机抽样无边的节点对。
评分方法:
开始胡思乱搞模式……
我:搞了半天突然发现本文的创新点概括成一句话就是对边的权重做了些微调整。怎么感觉如此 Fuck 简单呢?
大神:那你还想咋滴?创新可不就是那么一点点的修补吗?!要不你也来创新一个?
我:噢……(内心 OS:WTF,浪费了我一整天时间!)
仔细想想,感觉无论什么样的 node embedding,都是需要先获得一个序列,而很多算法也都在如何获得这个序列上下功夫。就直观感受来看,随机游走在图上显然是比较合适的方式,这其实也是一种随机采样。
词向量也是类似的方式,其实文字不也可以看作是语言的一种采样么?我们看到的每句话、每段文本,都可以看做是图中的一条路径,也可以看做一个采样序列。这样的话,我们看到的一篇文章其实就是一幅图,我们能否用这种图结构来表征文本?这样的图能否表现出某些自然倾向的特性?
alias_setup
是一个用于从离散分布中进行非均匀采样的工具,参考自这里,不过我已经打不开了。它的输入是一个归一化的概率分布,具体实现如下:
def alias_setup(probs):
K = len(probs)
q = np.zeros(K)
J = np.zeros(K, dtype=np.int)
smaller = []
larger = []
for kk, prob in enumerate(probs):
q[kk] = K*prob
if q[kk] < 1.0:
smaller.append(kk)
else:
larger.append(kk)
while len(smaller) > 0 and len(larger) > 0:
small = smaller.pop()
large = larger.pop()
J[small] = large
q[large] = q[large] + q[small] - 1.0
if q[large] < 1.0:
smaller.append(large)
else:
larger.append(large)
return J, q
和 alias_draw
联系起来就是根据概率分布取样:
res = []
probs = [0.1, 0.2, 0.7]
J, q = alias_setup(probs)
for i in range(100):
choose = alias_draw(J, q)
res.append(choose)
collections.Counter(res)
# 结果类似这样:Counter({2: 72, 1: 18, 0: 10}),大致接近 1: 2: 7
对了,random 的 choices 函数,numpy
的 random choice 函数均可以实现同样的功能:
collections.Counter(random.choices([0, 1, 2], weights=[0.1, 0.2, 0.7], k=100))
# Counter({2: 65, 1: 22, 0: 13})
collections.Counter(np.random.choice([0, 1, 2], size=100, replace=True, p=[0.1, 0.2, 0.7]))
# Counter({2: 68, 1: 23, 0: 9})
所以,其实本文的实现可以简化,直接把每个节点和边的 normalized_probs
存下来就好了,随机游走代码可以改为这样:
choose = np.random.choice(list(range(len(cur_nbrs))),
size=1, replace=True, p=curr_normalized_probs)
nxt = cur_nbrs[choose[0]]
另外,随机游走时,起始节点我觉得可以不用处理,直接换成起始边就好了。也就是这样:
for walk_iter in range(num_walks):
random.shuffle(edges)
for edge in edges:
walks.append(node2vec_walk(walk_length=walk_length, start_edge=edge))
联系客服