图表示学习:图嵌入

由于今年要着手一些图结合AI的工作,因此在此对一些经典文献做一些总结。

这是图表示学习(representation learning)的第一部分——图嵌入(graph embedding),主要涉及DeepWalk [KDD’14]、LINE [WWW’15]、node2vec [KDD’16]、KnightKing [SOSP’19]、GraphZoom [ICLR’20]五篇论文。

关于图数据挖掘/表示学习的内容强烈建议去看Stanford Jure LeskovecTutorial - Representation Learning on Networks (WWW’18)

Word Embeddding

先从NLP说起,当代基于深度学习的NLP取得巨大突破很大的原因是将高维离散的词语符号表示,转化为低维空间的连续分布式的语义表示。

举个例子,

我 爱 苹果

我 爱 雪梨

原来用数字索引或one-hot表示,一个词语就对应着一个数字(一维表示 $\mathbb{N}$),那么上面的4个词语就可以变成

  • 我 0 [1,0,0,0]
  • 爱 1 [0,1,0,0]
  • 苹果 2 [0,0,1,0]
  • 雪梨 3 [0,0,0,1]

但显然这种方法是无法表现出词语之间的相似性关系的,因此后来就有了更聪明的方法,考虑将这些词语用高维空间中的向量表示($\mathbb{R}^n$),如果两个词向量之间的距离近,那么它们对应的词就具有越高的语义相似性,这种思想即word2vec1

比如将上述四个词encode成以下几个3维向量

  • 我 [1,1,1]
  • 爱 [1,-1,1]
  • 苹果 [-1,1,0.5]
  • 雪梨 [-1,1,0.4]

那么可以直观地看出苹果和雪梨在语义上较为接近,因为都是水果。

在Pytorch的简单实现上,nn.Embedding实际上做的就是一个线性映射,其中的权重也是可以训练的。由于是one-hot输入,与矩阵相乘,因此作用相当于一个查找表(Look-Up Table),如下所示。

February 6, 2020 - 图表示学习(1)- 图嵌入

Graph Embedding

放到图(graph)上来说也是类似的,考虑图中的边表相似关系,如果两个结点之间的路径越短,则意味着这两个结点之间的相似度越高。如果仅仅用邻接矩阵表示图的相邻关系的话,是很难看出结点之间的相似关系的(至多看到一度关系)。

考虑图$G(V,E)$,在其基础上添加顶点的类别,则形成标注图(labeled graph)$G_L=(V,E,X_{em},Y)$,其中$X_{em}\in\mathbb{R}^{|V|\times d}$为顶点嵌入,$Y\in\mathbb{R}^{|V|\times |\mathcal{C}|}$,$d$为特征维数,$Y$为标签集。

注意这种写法指$X$和$Y$均为矩阵,$X$一共有$|V|$行,每行对应一个顶点的特征向量,有$d$维;并且每个结点可能属于多个类别$\subset \mathcal{C}$。(指multi-label classification,而不是multi-class每个样本只归属一类别)。

目标则是学习得到嵌入表示$X_{em}$,或者说映射$\Phi:V\mapsto X_{em}$,使得在低维的嵌入空间中,图结点有很好的分布式连续表达,能够很好保持图的邻接结构,即结点向量间的距离能够衡量原图中的邻接关系强弱

下图展现了一个2维图嵌入表示,可以看到如果图嵌入做得好,是能够很好保持原图结构的(该网络来源于著名的空手道俱乐部网络Karate network2,并用力导向方法进行呈现,结点颜色则是依据modularity进行的社群检测)。

既然也是做嵌入,那能否将既有NLP中成熟的词嵌入方法移植过来呢?于是就有了DeepWalk3

DeepWalk3

很简单的类比,就是将图上的结点当成是词语,而几个结点构成的连续路径则当成句子

那么问题就变成怎么找到这些合适的路径

Random walk

最早一批发表的图表示学习文章DeepWalk3就采用了随机游走(random walk)的方式,来生成这些路径,实际上就是从一个结点出发走$L$步到达另一个结点的路径。

形式化定义则令出发结点为$v_i$,随机游走是一个随机过程

\[\mathcal{W}_{v_i}:\mathcal{W}_{v_i}^1,\mathcal{W}_{v_i}^2,\ldots,\mathcal{W}_{v_i}^k\]

使得$\mathcal{W}_{v_i}^{k+1}$是从$v_k$的邻居中随机挑选出的结点。

随机游走的好处是明显的:

  • 并行性:显然可以同时开多个walker从不同结点出发进行游走
  • 适应性:可以轻松应对动态网络,一旦有网络结构更新,只要有足够多的walker进行重新采样,就可以对其嵌入表示进行更新

而通过随机游走,我们也可以发现图和文本的相似之处——它们都符合幂律/长尾分布(power law),或者说是scale free的。

February 6, 2020 - 图表示学习(1)- 图嵌入

Skip-gram

因此可以尝试套用NLP中的语言模型(Language Model, LM)来做结点嵌入。

LM的目标是估计特定序列/句子在语料中的出现概率,比如给定一个句子$W_1^n=(w_0,w_1,\ldots,w_n)$,那么最大化

\[\mathrm{Pr}(w_n\mid w_0,w_1,\ldots,w_{n-1})\]

在所有训练语料中的概率。

放在图中则变为给定随机游走的前$i-1$个结点,最大化$\mathrm{Pr}(v_i\mid (v_1,v_2,\ldots,v_{i-1}))$。

目标是学习结点的嵌入表示,而不仅仅是结点的共现(co-occurance)情况。引入映射函数$\Phi:v\in V\mapsto\mathbb{R}^{\vert V\vert \times d}=X_E$,估计下式

\[\mathrm{Pr}\left(v_i\mid (\Phi(v_1),\Phi(v_2),\ldots,\Phi(v_{i-1}))\right)\]

但由于计算量太大,所以需要采用其他方法。而该优化形式在NLP中已经被研究得很多,因此尝试采用NLP的方法来解决。

在word2vec4中提到了两种LM,一种CBOW,输入为前后$w$个词,输出为中间词;而另外一种是skip-gram,输入中间词,输出前后$w$,这可以大大减轻计算量,也是我们着重关注的。

如下图展现了窗口大小为2的情况,skip-gram可以用于生成词语之间的共现(cooccurance)情况。

February 6, 2020 - 图表示学习(1)- 图嵌入

最终得到优化问题为

\[\min_{\Phi}\;-\log\mathrm{Pr}(\{v_{i-w},\ldots,v_{i-1},v_{i+1},\ldots,v_{i+w}\}\mid\Phi(v_i))\]

注意这里符号的意思是在$[i-w,i+w]$区间上任取一个,即其将随机游走中的序给消除了。

其实到这里,整体的算法流程就很清晰了:

  1. 每次随机选择一个起始点$v_i$
  2. 从$v_i$开始,做长为$\vert\mathcal{W}_{v_i}\vert=t$的随机游走
  3. 依据得到的$\mathcal{W}_{v_i}$,做skip-gram。即对每一$v_j\in\mathcal{W}_{v_i}$,每一$u_k\in\mathcal{W}_{v_i}[j-w:j+w]$,做梯度下降更新参数

\[\begin{aligned}

J(\Phi)&=-\log\mathrm{Pr}(u_k\mid\Phi(v_j))\\

\Phi&=\Phi-\alpha\frac{\partial J}{\partial\Phi}

\end{aligned}\]

这里还有一些优化的地方:

  • 为了让SGD更快收敛,一般是将所有的顶点打乱后,再进行顺序遍历(如果完全随机,很难做到每个点都能被采样到)
  • 利用层次Softmax1来加快计算,即$\mathrm{Pr}(u_k\mid\Phi(v_j))=\prod_{l=1}^{\lceil\log\vert V\vert\rceil}\mathrm{Pr}(b_l\mid\Phi(v_j))$,其中$b_i$是二叉树的结点,$b_0$是根
  • 进一步可以利用Haffman编码来加快二叉树的访问
  • 由于顶点十分稀疏,更新也是稀疏的,故可以直接上异步SGD,甚至不用加锁

注意DeepWalk很强的一点在于它使用的是无监督方法,即只需知道图结构,就可以学出对应的隐含表示。

Experiments

DeepWalk分别在BlogCatalog、Flicker和YouTube三个数据集上做多标签分类,下面给出这三个数据集的基本数据,以便有一个直观感受。

NameBlogCatalogFlickrYouTube
$\vert V\vert$10,31280,5131,138,499
$\vert E\vert$333,9835,899,8822,990,443
$\vert Y\vert$3919547
LabelsInterestsGroupsGroups

可以看到这些数据集相比起Graph500的规模是非常小的。

各超参数的值也附在这里,作为参考。

$\gamma$$w$$d$
8010128

至于多标签分类,可见下图,即给出比如10%的标记结点作为训练集,剩下的90%则作为测试集。

February 6, 2020 - 图表示学习(1)- 图嵌入

得到隐含表示后,聚类则变得很简单,DeepWalk是采用了one-vs-rest的logistic回归来分类。最终的实验结果是非常好的,只用1%的训练数据,宏F1和微F1指标都远超之前的方法。

LINE 5

LINE采用了一阶相似度(proximity)和二阶相似度进行建模。

一阶相似度衡量邻居关系,如果两个结点有边相连,则这两个结点的一阶相似度高;二阶相似度则要看邻居的重叠关系,如上图的5和6,尽管没有边直接相连,但是它们有大量重叠的邻居,因此他们的相似度也非常高。

一阶相似度

考虑结点$v_i$和$v_j$有边$(i,j)$,定义联合概率

\[p_1(v_i,v_j)=\frac{1}{1+\exp(-\mathbf{u}_i^\top\cdot\mathbf{u}_j)}\]

其中$\mathbf{u}_i\in\mathbb{R}^d$为$v_i$的低维向量表示。直觉上如果两个向量足够近,那么这两个向量的点积应该很大(也即向量点积可以用于衡量相似度,类似于余弦相似度,只是将常数部分忽略);又为了让其表示概率,则用logistic函数进行映射。

可定义先验概率为$\hat{p}1(i,j)=\frac{w{ij}}{\sum_{(i,j)\in E}w_{ij}}$,即所有边中刚好选中$(i,j)$的概率。

为保一阶相似度关系,最直接的方法即衡量两个概率分布之间的距离

\[O_1=d(\hat{p}_1(\cdot,\cdot),p_1(\cdot,\cdot))\]

用KL散度代替距离并忽略常数,即

\[\min O_1=\min \left(-\sum_{(i,j)\in E}w_{ij}\log p_1(v_i,v_j)\right)\]

二阶相似度

如果两个结点的二阶相似度高,则意味着它们共享相同的邻居/上下文(context)。这样每个结点将会有两种角色,一种是它自己$\mathbf{u}_i$(中心词),另一种是其他结点的上下文$\mathbf{u}_i’$(背景词)。(在具体实现上即每个结点会有两个embedding。)对于有向边$(i,j)$,定义结点$v_i$在上下文$v_j$下的概率为(相当于Softmax)

\[p_2(v_j\mid v_i)=\frac{\exp(\mathbf{u'}_j^\top\cdot\mathbf{u}_i)}{\sum_{k=1}^{|V|}\exp(\mathbf{u'}_k^\top\cdot\mathbf{u}_i)}\]

先验概率$\hat{p}2 (v_j \mid v_i) = \frac{w{ij}}{d_i}$,其中$d_i = \sum_{k \in \mathcal{N}(v_i)} w_{ik}$为出度。

为保二阶相似度关系,则最小化(用KL散度代替)

\[O_2=\sum_{i\in V}\lambda_id(\hat{p}_2(\cdot\mid v_i),p_2(\cdot\mid v_i))

=-\sum_{(i,j)\in E}w_{ij}\log p_2(v_j\mid v_i)\]

优化(负采样)

本部分内容参照《动手学深度学习》-10.2近似训练,课程视频可见B站,原始论文见6

负采样修改了原来的目标函数。给定中心词 $w_c$ 的一个背景窗口,我们把背景词 $w_o$ 出现在该背景窗口看作一个事件,并将该事件的概率计算为

\[P(D=1\mid w_c, w_o) = \sigma(\boldsymbol{u}_o^\top \boldsymbol{v}_c)\]

这里$D=1$代表该事件发生。设背景词 $w_o$ 出现在中心词 $w_c$ 的一个背景窗口为事件 $P$ ,我们根据分布 $P(w)$ 采样 $K$ 个未出现在该背景窗口中的词,即噪声词/负样本。设噪声词 $w_k ( k=1,\ldots,K )$ 不出现在中心词 $w_c$ 的该背景窗口为事件 $N_k$ 。假设同时含有正类样本和负类样本的事件 $P,N1,\ldots,N_K$ 相互独立,负采样将以上需要最大化的仅考虑正类样本的联合概率改写为(最大似然函数)

\[\prod_{t=1}^{T} \prod_{-m \leq j \leq m,\ j \neq 0} P(w^{(t+j)} \mid w^{(t)})\]

其中条件概率被近似表示为(背景词出现在背景窗口的概率 乘上 噪声词不出现在背景窗口的概率)

\[P(w^{(t+j)} \mid w^{(t)}) =

\frac{P(w^{(t+j)},w^{(t)})}{P(w^{(t)})} \approx

P(D=1\mid w^{(t)}, w^{(t+j)})\prod_{k=1,\ w_k \sim P(w)}^K P(D=0\mid w^{(t)}, w_k)\]

设文本序列中时间步 $t$ 的词 $w(t)$ 在词典中的索引为 $i_t$ ,噪声词 $w_k$ 在词典中的索引为 $h_k$ 。有关以上条件概率的对数损失为

\[\begin{aligned}

-\log P(w^{(t+j)} \mid w^{(t)})

=& -\log P(D=1\mid w^{(t)}, w^{(t+j)}) - \sum_{k=1,\ w_k \sim P(w)}^K \log P(D=0\mid w^{(t)}, w_k)\\

=&- \log\, \sigma\left(\boldsymbol{u}_{i_{t+j}}^\top \boldsymbol{v}_{i_t}\right) - \sum_{k=1,\ w_k \sim P(w)}^K \log\left(1-\sigma\left(\boldsymbol{u}_{h_k}^\top \boldsymbol{v}_{i_t}\right)\right)\\

=&- \log\, \sigma\left(\boldsymbol{u}_{i_{t+j}}^\top \boldsymbol{v}_{i_t}\right) - \sum_{k=1,\ w_k \sim P(w)}^K \log\sigma\left(-\boldsymbol{u}_{h_k}^\top \boldsymbol{v}_{i_t}\right).

\end{aligned}\]

现在,训练中每一步的梯度计算开销不再与词典大小相关,而与 $K$ 线性相关。当 $K$ 取较小的常数时,负采样在每一步的梯度计算开销较小。

为了让生僻词更容易被采样,通常取$P_n(w)\thicksim U(w)^{3/4}/Z$。举例来说$w$的单字概率为$0.01$,则$0.01^{3/4}=0.03$会变大。

放到LINE模型中则是最小化

\[\log\sigma(\mathbf{u}_j^\top\mathbf{u}_i)+\sum_{i=1}^{K}\mathbb{E}_{v_n\thicksim P_n(v)}[\log\sigma(-\mathbf{u'}_n^\top\cdot\mathbf{u}_i)]\]

代码实现

可见DGL的官方代码库

训练的入口函数为见line.py,用with torch.no_grad()包裹,代表不需要跟踪梯度信息。

先采负边(neg_nodes),然后调用model.pyfast_learn

得到正边的$\mathbf{u}$和$\mathbf{v}$,见L369-L371,通过fast_pos_bp直接得到回传梯度。同理负边算梯度,见L309-L334

注意emb_uemb_v只包括对应的正/负边结点的embedding,因此后面要通过index_add_将对应结点更新后的embedding加回去。

node2vec7

目标和DeepWalk一样,也是自动地学习结点特征,生成隐含表示(latent representation)

传统的方法常常是有监督的,需要人工进行特征工程,会加入大量前提假设;或者直接采用PCA等方法对图的邻接/Laplace矩阵进行变换,但是矩阵分解工程量很大,可扩展性极低。

而DeepWalk一个很明显的缺点就是它均匀地对每个结点的邻居进行采样,这样会造成其无法很好控制其访问的邻居,因此node2vec的最大改进之处就是将采样方式给参数化了。

形式化地来说,对于每一源结点$u\in V$,定义其由采样策略$S$得到的邻居为$N_S(u)\subset V$(这里一定要注意,采样策略得到的邻居并不一定是直接邻居,后面会再阐述),希望在给定嵌入表示的前提下,最大化该邻居出现的概率,即

\[\max_\Phi\sum_{u\in V}\log\mathrm{Pr}(N_S(u)\mid \Phi(u))\]

为了解决上述优化问题,又有以下假设:

  • 条件独立性:即邻居之间都相互独立

\[\mathrm{Pr}(N_S(u)\mid\Phi(u))=\prod_{n_i\in N_S(u)}\mathrm{Pr}(n_i\mid\Phi(u))\]

  • 特征空间对称性:源结点和其邻居在彼此的特征空间中应该有对称的影响,因此用点积进行模拟($a\cdot b=b\cdot a$),有softmax函数

\[\mathrm{Pr}(n_i\mid f(u))=\frac{\exp(\Phi(n_i)^T \Phi(u))}{\sum_{v\in V}\exp(\Phi(v)^T \Phi(u))}\]

结合上述假设,优化问题变为

\[\max_\Phi\sum_{u\in V}\left[-\log Z_u+\sum_{n_i\in N_S(u)}\Phi(n_i)^T \Phi(u)\right]\]

其中$Z_u=\sum_{v\in V}\exp(\Phi(v)^T \Phi(u))$计算量非常大,采用负采样(negative sampling)1的方法进行优化。

Equivalance

在预测任务中其实主要关注两种相似性:

  • 同质性(homophily equiv):相互连结或同属一个社群的结点,其嵌入应比较靠近,如下图的$s_1$和$u$
  • 结构性(structural equiv):在社群中扮演同样的角色的结点,其嵌入应比较靠近,如下图的$u$和$s_6$都是各自社群的中心结点

February 6, 2020 - 图表示学习(1)- 图嵌入

而用BFS和DFS就可以分别生成对应的相似性,这里直观理解可能容易理解反,因此参考知乎的评论

BFS(微观特性):对于两个结构性比较类似的结点,BFS构建两个节点在类似位置的context序列的概率更高,因此可以更好的学习到结构性;进一步假设,如果两个点有大量相同的邻居节点,那么node2vec训练时,具有相同context的概率更高,embedding向量应该更接近

DFS(宏观特性):对于两个距离比较近的节点,出现在相同sequence context的几率比较高,因此近距离的节点容易学习出相似的embedding向量

2nd-Order Random Walk

下图则是node2vec的精髓,其定义了一个带$p$和$q$两参数的二阶随机游走,在每个结点处访问不同邻居的概率是不同的。

其考虑的是二阶邻居的关系$t\to v\to x$,$t$到$x$的最短距离$d_{tx}$只能是${0,1,2}$三个值(比原来更近、和原来一样、比原来更远)。

那么可定义搜索偏差(search bias)

\[\alpha_{pq}(t,x)=

\begin{cases}

\frac{1}{p} & ,d_{tx}=0\\

1 & ,d_{tx}=1\\

\frac{1}{q} & ,d_{tx}=2

\end{cases}\]

其中,

  • $p$为return参数,控制在随机游走中立即返回上一结点的概率,如果设得很大($>\max(q,1)$),则意味着更大机率往外走,且避免2-hop内的重复采样
  • $q$为in-out参数,控制在随机游走中往外/内走的概率,如果设得很大($>1$),则更倾向于往里走(BFS);否则,则倾向于往外走(DFS)

最后进行归一化,可得到随机游走的转移概率

\[\mathrm{Pr}=(c_i=x\mid c_{i-1}=v)=

\begin{cases}

\frac{\alpha_{pq}(t,x)\cdot w_{vx}}{Z} & (v,x)\in E\\

0 & \mathrm{otherwise}

\end{cases}\]

其中$w_{vx}$为边权。

随机游走比传统的BFS和DFS具有空间和时间复杂性的好处(依照原文),但这里存疑,暂缓不表。

综上就有了node2vec的算法,相比起DeepWalk,它将三个阶段彻底分离,更加方便每个阶段的并行。

  1. 预处理计算转移概率
  2. 生成大量随机游走
  3. 利用这些游走进行SGD

node2vec还有一个创新之处在于,其将无监督嵌入表示方法拓展到了连边预测上。

其实有了结点的嵌入表示$\Phi(u)$和$\Phi(v)$后,构造边的嵌入也比较简单,即将这两者做一个二元操作

\[g(u,v)=\Phi(u)\circ\Phi(v): V\times V\mapsto\mathbb{R}^{d'}\]

Experiments

最后的实验也做得很详实,果然数据挖掘顶会的平均水准还是远高于AI顶会的(10页双栏,与系统会议类似)。

实验主要包括以下几个部分

  1. 在Les Misérables网络上对BFS/DFS随机游走的可视化(用k-means聚类),上图展现同质性,下图展现结构性

    February 6, 2020 - 图表示学习(1)- 图嵌入

  2. 实验设置(Spectral clustering, DeepWalk, LINE),C/C++/Python实现, http://snap.stanford.edu/node2vec
  3. 多标签分类
  4. 敏感性分析
  5. 扰动(perturbation)分析(缺信息情况下的表现)
  6. 可扩展性(采样占据了绝大多数时间,优化的时间其实比较小,这才有了后面KnightKing的工作)
  7. 连边预测

最终实验结果也是吊打前者,故在此不再赘述。

KnightKing8

从前面的叙述可以看出,虽然随机游走取得了很好的效果,但是其采样的部分占据了绝大多数训练时间,因此如何对随机游走的采样进行加速就变成了一个重要的问题。

而随机游走实际上是一个图计算的问题,因此可以用图计算系统来解决,包括单机的Ligra、分布式的Gemini等,但是这些图系统基本是以顶点为中心(vertex-centric)的,没有办法很好地解决随机游走的问题(主要原因是难以记录整条路径),故有了KnightKing这一以游走者为中心(walker-centric)的图计算引擎。

Random Walk Taxonomy

要建起一个针对随机游走都通用的系统,最关键一步就是找这些算法的共通之处,然后进行抽象,得到统一表达。

首先进行算法的分类,从转移概率来说,随机游走可分为

  • 无偏(unbiased):均匀分布
  • 有偏(biased):转移概率依赖边权
  • 静态:转移概率在游走过程中不会改变(无状态stateless)
  • 动态:转移概率会因游走过来时的路径而改变(有状态)

    • 进而可分阶次(order),一阶只关乎当前节点,为静态;二阶关心过来的邻居,为动态;高阶以此类推

然后可用统一的转移概率公式来表达(注意这里并未做归一化)

\[P(e)=P_s(e)\cdot P_d(e,v,w)\cdot P_e(v,w)\]

这是十分直接的公式化,即某一条出边$e$的转移概率,等于静态成分、动态成分、扩展成分三者相乘。

详细地说,游走者$w$当前处于结点$v$,

  • 静态成分$P_s$只关乎当前的边$e$
  • 动态成分$P_d$关乎这条边以及游走者过来的路径/状态($w$含有$v$之前所有的状态)
  • 扩展成分$P_e$则不与出边相关(这里可能是为了解决其他一些未考虑到的情况,这一项的形式化方法存疑)

那么一些随机游走的算法就可以通过这三项轻松表达,其中$P_e(v,w)$被设置成到达最大长度($\vert w+v\vert =L$)则返回0,其余两项的取值如下表所示($w_e$指边$e$的边权)

$P_s(e)$$P_d(e,v,w)$
DeepWalk$1$ or $kw_e$$1$
Meta-path$kw_e$$\begin{cases}1 & \text{if }type(e)=S_{k\mod\vert S\vert} \\ 0 & \text{otherwise}\end{cases}$
node2vec$kw_e$$\begin{cases}\frac{1}{p} & ,d_{tx}=0 \\ 1 & ,d_{tx}=1 \\ \frac{1}{q} & ,d_{tx}=2\end{cases}$

Existing Optimization

对于静态的随机游走,常见的采样方法有以下两种

February 6, 2020 - 图表示学习(1)- 图嵌入

  • ITS:计算边转移概率的累积概率分布,然后抽随机数,二分查找看落在哪个区间(假设$n$条出边,则$O(n)$时间空间建立查找表,$O(\log n)$时间查找)
  • Alias:将每条边分成多份,放入不同的桶中,确保每个桶至多两条边且总和相同。采样时随机采样一个桶,然后随机采样两条边中的一条即可(同样$O(n)$预处理时间,但只需$O(1)$时间查找)

但这个时空开销对于动态游走来说都是不合适的,因此传统的深度学习系统(Tensorflow)也不能很好处理,可扩展性极低。进而现在更多关于随机游走的优化是从算法层面实现的,通过近似采样,实现复杂度的降低。

Sampling

抽象只是解决了编程一致性的问题,但怎么算得快依然是没有解决的,而下面的部分才是本论文最高能的地方。

论文作者翻出了一篇几十年前的文章,专门讲从任意的概率分布中采样的方法,然后他们成功地将该论文的方法用到随机游走采样上并获得了奇效。这种采样方法称之为Rejection Sampling,参见下图。

February 6, 2020 - 图表示学习(1)- 图嵌入

核心思想是将1维的概率采样,转化为2维的采样(想想前面的两种优化方法,ITS算是1D的,Alias算半个2D,因为确实要采样两次,但是却把查找的时间复杂度降了下来)。

  1. 建立概率分布,间隔为1,高度即为每条边的转移概率(未归一化)
  2. 选取一个最大的信封(envelop),可以框住所有的概率分布
  3. 在2D空间随机撒点,落在概率分布内接受采样,否则拒绝
  4. 拒绝则继续重复3,直至采样成功

正确性保证在下面书中有

David JC MacKay and David JC Mac Kay. 2003. Information theory, inference and learning algorithms. Cambridge university press.

看上去好像跟原来的1D采样也没什么不同,但是细想一下,就会发现rejection sampling很牛逼。

因为原来你都是需要将所有转移概率算出来,然后才采样,看落在哪个区间;但现在是先采样,然后再判定是否符合要求。前者需要检查所有出边,而后者只需检查一条边,时间复杂度瞬间降下来了。(而且注意这种方法是精确采样而不是取近似哦)

上面图中的例子只是无偏的,如果考虑有偏,那只需更改每个小矩形的宽即可。而前面的抽象正好也给了这种对应机会,即小矩形的宽是$P_s$,而小矩形的高是$P_d$,由于信封高度$Q(v)$为$P_d$的最大值,而这些在随机游走算法中是确定的(比如node2vec就是$1/p$、$1/q$和$1$三者的最大值),因此采样只需先判x落在哪个$P_s$区间中(这里用1D的采样方法即可解决),然后直接采$y$,判断$y$是否小于$P_d$,即可判接受还是拒绝。显而易见,这种方法对于动态随机游走是没有多余的预处理时间的(如累加),只需一开始将$P_s$处理好即可(存在一个数组中)。

这种方法的核心问题/开销在于如何快速地采样到有效区域,因此后面的优化也是trivial的。

February 6, 2020 - 图表示学习(1)- 图嵌入

  • 将过高矩形(outlier)进行裁剪补到后面以降低$Q(v)$,如上图所示。但是这种方法有很严重的问题是不知道到底要裁剪多少,因为你现在只采样了一个矩形,frankly来说你是不知道其他矩形的情况的(文中脚注作者说是设一个threshold,当成超参数让用户自己调。这种方法看上去就是根据node2vec这种特殊情况进行适配的,因为只有三个概率取值,因此可以很好估计最大值多少,去除最大值之后应该怎么剪);另一方面,一次裁剪就足够了吗,如果一次裁剪依然是非常高的矩形那又应该怎么办呢,本文似乎回避了这个问题,或者说认为这种情况发生概率非常小。
  • 另外一个优化则是针对低矩形的,如果采样比所有矩阵都低,那当然就可以直接确认了,谓之为pre-acceptance(但似乎这一个优化只是减少了一个比较操作吧…)

编程模型的API就不说了,毕竟就是那几个参数怎么设的问题。

Experiments

不比前面那些算法论文只跑小图,KnightGraph跑了真实的大规模图,最大的是UK-Union,有134M个顶点,5.51B条边,估计在几十G的大小。

实验没有测端到端,只是测了路径采样的部分;并且没有跟深度学习框架(Tensorflow)等比,只跟Gemini比了,在动态采样上达到了惊人的4个阶的加速比提升,当然这也是可预见的(其实这完全归功于算法)。

Summary

本文诠释了一个好的idea就能出一篇paper,其余的工作其实都是工程实现。总结来说就三个贡献点:

一个简单通用的抽象(系统层面)+好的采样方法(算法层面)+实验

同时也可以看出,算法提升带来的收益远大于系统层面优化带来的收益,“系统设计是重要的,但算法设计同样也很重要”。

C-SAW9

三个挑战(前两点存疑):

  1. 采样与传统图计算的却别:传统图计算对不同边/点等同对待,而采样常常要考虑bias,重点在如何选点上
  2. 很难实现大一统GPU采样框架
  3. 大图超出GPU memory

本文则是提出了一个GPU的图采样和随机游走框架。

无论是图采样还是随机游走,他们都 1) 以遍历为中心,2) 基于bias选择性采点。

下面是几种常见的基于bias的采点方式。

February 6, 2020 - 图表示学习(1)- 图嵌入

提供了以下3个API供用户实现不同的采样算法。

February 6, 2020 - 图表示学习(1)- 图嵌入

GPU优化

Warp-Centric Parallel Selection

  • 在Warp内部并行采样,而不是开block,因为大多数点的degree并不大
  • Inverse transform sampling + 并行前缀和
  • 采样冲突(需要保证采的边不同):Bipartite Region Search,同时维护Strided Bitmap来记录哪些点访问过了(考虑memory bank的并行方案)

February 6, 2020 - 图表示学习(1)- 图嵌入

图划分

直接采用range partition(结点等分),该结点的所有边都被归到当前partition,1)保持良好局部性,2)避免大量预处理开销。

由于GPU内存有限,因此这里的问题是如何选择/调度partition进GPU内进行计算,本文提出了Workload-Aware Partition Scheduling,核心idea是先做active nodes多的partition,因为active nodes扩展出来的新结点也会很多,将这个partition算完再换下一个的收益就很大。

February 6, 2020 - 图表示学习(1)- 图嵌入

由于点和点之间互相独立,因此可以轻松将C-SAW扩展到多GPU进行计算。

实验

最大的图为Friendster和Twitter,性能与KnightKing和GraphSAINT比较。

GraphZoom10

Reference

  1. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, Jeffrey Dean (Google), Distributed Representations of Words and Phrases and their Compositionality, NeurIPS, 2013  2 3
  2. Wayne W. Zachary, An Information Flow Model for Conflict and Fission in Small Groups, Journal of Anthropological Research, 1977 
  3. Bryan Perozzi, Rami Al-Rfou, Steven Skiena (Stony Brook), DeepWalk: Online Learning of Social Representations, KDD, 2014  2 3
  4. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, Jeffrey Dean (Google), Efficient Estimation of Word Representations in Vector Space, arXiv:1301.3781v3 
  5. Jian Tang (MSRA), Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, Qiaozhu Mei, LINE: Large-scale Information Network Embedding, WWW, 2015 
  6. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, Jeffrey Dean (Google), Distributed representations of words and phrases and their compositionality, NeurIPS, 2013 
  7. Aditya Grover, Jure Leskovec (Stanford), node2vec: Scalable Feature Learning for Networks, KDD, 2016 
  8. Ke Yang, MingXing Zhang, Kang Chen, Xiaosong Ma, Yang Bai, Yong Jiang (Tsinghua), KnightKing: A Fast Distributed Graph Random Walk Engine, SOSP, 2019 
  9. Santosh Pandey (Stevens Institute of Technology), Lingda Li, Adolfy Hoisie, Xiaoye S. Li, Hang Liu, C-SAW: A Framework for Graph Sampling and Random Walk on GPUs, SC, 2020 
  10. Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang (Cornell), Zhuo Feng, GraphZoom: A Multi-Level Spectral Approach for Accurate and Scalable Graph Embedding, ICLR (Oral), 2020 

以上是 图表示学习:图嵌入 的全部内容, 来源链接: utcz.com/a/128226.html

回到顶部