BLOG

个人博客,记录学习与生活

[KDD2016]Node2Vec

Published July 24, 2020, 6:04 p.m. by kkk

生成节点的网络邻居方法:改进对网络中节点邻节点的采样策略,采用2阶序的随机游走,综合广度和深度探索,更好地获取节点的网络结构

特征学习框架

类似于NLP优化思路(和skipgram思路就是完全一样),MLE $$ \max_f \sum_{u\in V} \log Pr(N_s(u)|f(u)) $$ 其中$N_s(u)$为采用某采用策略得到的点$u$的邻居节点集合,为了方便问题处理,提出如下两个假设:

  • 条件独立性,各节点被观察到的概率是独立的

$$ Pr(N_s(u)|f(u)) = \prod_{n_i\in N_s(u)} Pr(n_i|f(u)) $$

  • 特征空间的对称性,源节点和邻节点在特征空间中具有对称效应

$$ Pr(n_i|f(u)) = \frac{\exp(f(n_i) \cdot f(u))}{\sum_{v\in V} \exp(f(v) \cdot f(u))} $$

然后通过负采样SGD求解

核心思路

同质性(homophily)结构等价性(structural equivalence):论文提出,图上的节点预测任务通常与节点间的同质性和结构等价性相关,同质性假设指的是高度互联且属于同一网络集群或社区的节点嵌入后应该距离比较近(如上图中$u$和$s_1$),而结构等价性假设指具有相似网络结构的节点嵌入后距离比较近(如上图中的$u$和$s_6$)。这两个都具有很高的重要性,严格的BFS和DFS搜索都不能兼顾两者,而综合BFS和DEF能够更靠近这个目标。

综合BFS和DFS,定义二阶序随机游走(2nd order random walk):具有参数p和q的随机游走,选择的不同类型节点的概率不同。如图是刚刚遍历完边$(t,v)$的随机游走,正处于点$v$,到各点的非规范化概率为 $$ \pi_{vx} = \alpha_{pq}(t, x) \cdot \omega_{vx} $$

$$ \alpha_{pq}(t,x)= \begin{cases} \frac{1}{p} &\mbox{if $d_{tx}=0$}\\ 1 &\mbox{if $d_{tx}=1$}\\ \frac{1}{q} &\mbox{if $d_{tx}=2$} \end{cases} $$

如此设置之后,$\pi_{vx}$是二阶马尔科夫的,即下一步只有前两步的情况有关。对于长度为$l$的随机游走采样,对于$l-k$个节点,每次可以生成$k$个样本。

边特征的学习

对于预测任务,通常需要预测两点之间是否有边存在,如果训练得到的是边特征,以此可以更方便处理此类问题。

再现有算法基础和结果上,可以通过自助法(bootstrapping)将单个节点扩展成节点对。给定两个节点$u,v$和其特征$f(u), f(v)$,通过定义的二元运算(如下图)生成边的表示$g(u,v)$,满足($d^\prime$是边特征的维度): $$ g: V\times V \rightarrow \mathbb{R}^{d^\prime} $$

执行流程

  1. 转移概率的预计算
  2. 随机游走模拟
  3. SGD优化

上面三个步骤是顺序执行的,但每个步骤都可以并发、异步执行的,提高了算法的拓展性和并发性

性能

通过多标签分类、链接预测在几个进行试验


  1. Grover A, Leskovec J. node2vec: Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016: 855-864. 


Share this post
< Pre: [WWW2015]LINE Pos: [KDD2016]SDNE >
No comments
Similar posts
Add a new comment