阳江招聘网:【图机械学习】cs224w Lecture 7 - 节点的示意

admin 2个月前 (04-16) 科技 7 0

目录
  • Node Embedding
  • Random Walk
  • node2vec
  • TransE
  • Embedding Entire Graph
    • Anonymous Walk
  • Reference

转自本人:https://blog.csdn.net/New2World/article/details/105536633

Node Embedding

上一讲先容了对图中节点举行分类的方式,涉及了节点自身的特征以及图的结构信息。然而当特征这个观点泛起就说明需要做特征工程,这是相当费时艰苦的事情。最后的效果还不一定理想,由于或多或少会丢失一些信息。因此我们希望能让算法自己学习节点特征,虽然这样的到的特征向量并不像传统意义上的特征那样每一列有明确的意义,而更有一种对节点举行编码(embedding)的味道。其中最简朴的例子就是 one-hot,但这种简朴 embedding 的方式存在许多问题,好比泛化性差,维度高,信息缺失等。因此我们希望获得的 embedding 有一些很好的性子,好比 embedding 的相似度能反映节点在网络中的相似度。这里的相似度是凭据差别应用场景举行界说的,可以是拓扑结构上的相邻,也可以是之前提到的相同的角色。embedding 的相似度盘算也需要针对不用应用场景或需求来界说,但一样平常情况下接纳的照样向量的内积。
有了这个大要思绪我们就可以将这个学习节点 embedding 的历程简朴分为 3 步:

  1. 界说一个编码器
  2. 界说节点的相似度
  3. 对编码器的参数举行优化,使得 \(similarity(u,v)\approx z_v^Tz_u\)

Random Walk

随机游走,正如这个名字形貌的那样,节点从一个点最先沿着图中的边“乱”跑,途经的节点的 multiset(节点可重复) 就是我们想要的器械。为什么我们要这种看似无章可循的“乱”天生的效果?这实在是界说节点相似度的一种方式。假设现在我们需要节点 \(u\) 的 embedding,且我们希望节点相似度界说为结构上较为靠近的点具有更高相似度。那最容易想到的方式就是毗邻节点,这些点的相似度一定很高,这要能最大化这一部分点的 embedding 相似度就好了。想法很好也很准确,然则这样做存在两个问题。首先,若是只找毗邻节点,那获得的信息就只有 \(1\) hop,这样获得的效果太局限了。再说直观上也说不通,就好比和节点 \(u\) 直接相连的节点和 \(u\) 很类似,而 \(u\) 毗邻点的毗邻点就和 \(u\) 完全没有关系了。那可能就有人说,大不了我多迭代几回,思量跑个 \(k\) hop。那么这就涉及到第二个问题,对于大规模的网络一部分节点的度很高,例如微软 MSN 的网络最高的度是指数级别的,因此找所有毗邻节点价值太高更别说还要找毗邻点的毗邻点了。
这么一来,这个随机游走看起来是不是就很漂亮了。首先它随机流传,只要我们控制好流传距离就能实现多 hop。其次它不要求遍历所有毗邻点,但只要随机次数足够它照样能笼罩大部分毗邻点。
然后凭据随机游走的效果来界说相似度就很简朴了,即节点 \(u\)\(v\) 的 embedding 相似度和这两个节点同时泛起在随机游走的效果中的概率成正比。你细品是不是这个原理。
有了相似度,接下来就是优化的历程。我们用 log-likelihood 来做。这里将随机游走的效果记为 \(N_R(u)\)

\[\begin{aligned} \min L&=-\sum_{u\in v}\log P(N_R(u)|z_u) \\ &=\sum_{u\in V}\sum_{v\in N_R(u)}-\log P(v|z_u) \end{aligned}\]

然后由于是概率,以是我们用 softmax 来界说 \(P(v|z_u)\)

\[P(v|z_u)=\frac{\exp(z_u^Tz_v)}{\sum_{n\in V}\exp(z_u^Tz_n)} \]

为什么是 softmax ?
由于 \(\sum_i\exp(x_i)\approx\max_i\exp(x_i)\)

然而就算 numpy 再利便再快也经不起套娃的 sum 那 \(O(|V|^2)\) 的庞大度呀。于是接纳了 negative sampling 的方式取代每次盘算所有节点相似度和的步骤。negative sampling 说白了就是从所有节点中根据漫衍 \(P_V\) 随机选点。在这个场景下,每个点被选中的概率和它自身的 degree 成正比。

\[\log(\frac{\exp(z_u^Tz_v)}{\sum_{n\in V}\exp(z_u^Tz_n)})\approx\log\sigma(z_u^Tz_v)-\sum\limits_{i=1}^k\log\sigma(z_u^Tz_{n_i}) \]

随机选一些点不是会损失许多精度吗?看起来是的,但实际上这样做没什么问题。为什么?这个历程很庞大,有空我再去看,paper 链接先放这儿 https://arxiv.org/pdf/1402.3722.pdf
这里的 \(k\) 是 negative sampling 选点的超参数,一样平常来说 \(k\)\(5\)~\(20\)。太高的 \(k\) 虽然能获得更稳固的效果,但 bias 会增添,由于选点概率和度成正比。

node2vec

上面提到的这种是长度牢固的无偏随机游走。它的约束太强了导致获得的 embedding 泛化能力有限。这也是一个很主要的点,即更宽松的约束条件下获得的 embedding 更厚实。接下来先容的这个也是随机游走,但它的规则不一样。slide 里先容的这是一个有偏的二阶随机游走,有偏会在下面先容,但这里我是没看出来那里体现了二阶。
node2vec 里有两个要害超参数,return \(p\) 和 in-out \(q\)。下图很直观地展示了这两个参数的用途。首先从 \(s_1\) 出发到达 \(w\) 后需要决议下一步走那里,我们按 \(1/p\) 的相对概率回到 \(s_1\)\(1\) 的相对概率举行 BFS 即 \(s_1\) 的下一个毗邻节点,或者按 \(1/q\) 的相对概率流传出去即 DFS。如此一来就能 capture 到局部和全局特征了。这种方式在节点分类义务里效果很好。
注重,这里并不是概率,而是相对概率关系。

接下来就是用 SGD 做优化了。

TransE

TransE 实在也是一个学习节点 embedding 的算法。我对这个算法对照感兴趣,由于我一直想涉足知识图谱领域,而且我本科导师带的研究生就在做 TransE 相关的器械,我也或多或少领会过一点它的神奇特征。好比现在我们的图谱里有几个实体:“北京”,“中国”,“华盛顿”,“美国”;同时另有关系:“中国”\(\rightarrow\)“北京”,“美国”\(\rightarrow\)“华盛顿”。显而易见这个关系实在是“首都”的寄义,那么 TransE 能做到 “中国” - “北京” = “美国” - “华盛顿” = “首都” (固然,实在并没有“首都”这么一个实体,只是利便注释)。而这一特征就能完成 link prediction 的义务。好比我现在有“巴黎”和“法国”但没有这两个实体见的关系,那我们可以做的就是盘算出 “法国” - “首都” 然后盘算获得的效果和其它都会实体的相似度,而最终会发现“巴黎”的相似度最高。
之以是 TransE 能做到这一点,跟它的盘算方式有关。它并非接纳的随机游走的方式,而是接纳上面说到的这种特征来做的优化。首先将实体和关系界说为三元组 \((h,l,t)\),划分示意头实体、关系和尾实体 (有向)。然后

由此可见,随机游走并不是天生节点 embedding 的唯一方式,条条大路通罗马。

Embedding Entire Graph

最后一部分对整个图做 embedding 讲得很慌忙,我之前也没有太多体贴过这个问题。不外凭据 slide 自己理解了下。大致有三种方式

  1. 暴力求和
  2. 虚拟点示意图或子图,然后用尺度的 embedding 方式来做。参考 Li et al., 2016
  3. Anonymous walk

Anonymous Walk

这个玩意儿很神奇。它的界说和海内小学语文题类似,好比写出形如 AABB 的词语。然则这样的话有个疑惑,图中的 ABCDE 是怎么标的?事先有标签?照样怎么做?不是无监视学习吗?这需要看看论文再回来解决。

行使 anon. walk 也有几种方式来 embed 整个图。

第一种方式,我们先枚举出长度为 \(l\) 的所有 anon. walk,然后将图的 embedding 示意为这些游走的概率漫衍。好比长度为 \(3\) 的话就有 \(5\) 中排列,那么图的 embedding 就是一个 5D 向量。

第二种方式,我们天生 \(m\) 个随机游走的效果,然后凭据这个效果盘算履历漫衍。而这个 \(m\) 的取值是有下界的,我们希望误差大于 \(\varepsilon\) 的概率小于 \(\delta\) 的话

\[m=\lceil\frac2{\varepsilon^2}(\log(2^\eta-2)-\log(\delta)\rceil \]

其中 \(\eta\) 是长度为 \(l\) 的 anon. walk 的个数。

第三种方式,既然是机械学习那何不连游走历程一起学了?这里的 idea 是希望能编码游走历程使得下一个游走能被展望,即 \(P(w_t^u|w_{t-\Delta}^u,...,w_{t-1}^u)\) 这里的 \(w_t^u\) 是从节点 \(u\) 出发的第 \(t\) 个随机游走。

  1. 从节点 \(u\) 最先跑 \(T\) 次 Rnd walk 获得 \(N_R(u)=\{w_1^u,w_2^u,...,w_T^u\}\)
  2. 然后给定长度为 \(Delta\) 的滑窗,让算法学着展望在滑窗内同时泛起的 walk

\[\begin{aligned} \max\frac1T\sum\limits_{t=\Delta}^T\log P(w_t|w_{t-\Delta},...,w_{t-1}) \\ P(w_t|w_{t-\Delta},...,w_{t-1})=\frac{\exp(y(w_t))}{\sum_i^n\exp(y(w_i))} \\ y(w_t)=b+U(\frac1{\Delta}\sum\limits_{i=1}^{\Delta}z_i) \end{aligned}\]

这里 \(b\in\R\)\(U\in\R^D\)\(z_i\) 是 anon. walk 的 embedding。详细参考 Anonymous Walk Embeddings, ICML 2018

Reference

[1]: 这儿有一篇关于种种 embedding 方式的 survey:Goyal and Ferrara, 2017

,

Sunbet

Sunbet www.1888ss.com是24小时不间断资讯平台,能够迅速深度追踪社会主流新闻,持久关注追踪热点话题,联播各界新闻资讯,能够全面把握并精准推送给用户社会所关注的要点,为您提供最全最新的热点信息,更新内容短小精悍的政、商等社会各界头条新闻,让您在短时间内足不出户就能够迅速掌握新闻脉络,获得您关注新闻的最新进展。

Allbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:阳江招聘网:【图机械学习】cs224w Lecture 7 - 节点的示意

网友评论

  • (*)

最新评论

站点信息

  • 文章总数:437
  • 页面总数:0
  • 分类总数:8
  • 标签总数:970
  • 评论总数:117
  • 浏览总数:3358