刚哥的公开课笔记：图机器学习（七）图表示学习

图中的机器学习

节点分类

例子：链接预测

机器学习的生命周期：

监督学习生命周期每次都需要特征工程！

图中的特征学习

目标：高效的独立于任务的特征学习，以使用图进行机器学习！

为什么使用网络嵌入 network embedding

  • 任务：我们将网络中的每个节点映射到低维空间
    • 节点的分布式表示
    • 节点之间嵌入的相似性表明它们的网络相似性
    • 编码网络信息并生成节点表示

节点嵌入的例子

Zachary空手道俱乐部网络节点的2D嵌入：

Image from: Perozzi et al. DeepWalk: Online Learning of Social Representations. KDD 2014.

这玩意为啥很难？

  • 现代深度学习工具箱设计用于简单序列或网格。
    • CNN用于固定大小的图像/网格……。
    • RNN或word2vec用于文本/序列…

但是网络要复杂得多！

  • §复杂的地形结构（即没有像网格这样的空间局部性）
  • 没有固定的节点顺序或参考点（即同构问题）
  • 通常是动态的并具有多模式特征。

节点嵌入

  • 假设我们有一个图G：
    • V是顶点集。
    • A是邻接矩阵（假定为二进制）。
    • 不使用任何节点特征或其他信息

目标是对节点进行编码，以使嵌入空间（例如点积）中的相似度近似于原始网络中的相似度

学习节点嵌入：

  1. 定义编码器（即，从节点到嵌入的映射）
  2. 定义节点相似性函数（即原始网络中的相似性度量）
  3. 优化编码器的参数，以便：

两个主要的组件：

  • 编码器：将每个节点映射到低维向量
  • 相似度函数：指定向量空间中的关系如何映射到原始网络中的关系

“浅”编码

  • 最简单的编码方法：编码器只是一个嵌入查找

最简单的编码方法：编码器只是一个嵌入查找

每个节点都分配有唯一的嵌入向量

许多方法：DeepWalk，node2vec，TransE

  • 方法的关键选择是它们如何定义节点相似性。
  • 例如，如果两个节点具有类似的嵌入，则它们……。
    • 连接？
    • 分享邻居？
    • 具有类似的“结构角色”？
    • …？

以随机游走的方式来实现节点嵌入

给定一个图和一个起点，我们随机选择它的一个邻居，然后移动到该邻居。然后我们随机选择该点的邻居，然后移至该点，依此类推。以这种方式选择的点的（随机）序列是图形上的随机游动。

  • 使用估计从节点u开始的随机游历中访问节点v的概率一些随机游走策略R
  • 优化嵌入以对这些随机游走统计信息进行编码：
  • 相似度（此处：点乘积= cos（θ））编码随机游走“相似度”

为什么要随机游走？

  • 可表达性：节点相似性的灵活随机定义，结合了本地和高阶邻域信息
  • 效率：训练时不需要考虑所有节点对；只需要考虑随机游走同时发生的对

无监督特征学习：

  • 直觉：找到节点到d维的嵌入，保留相似性
  • 想法：学习节点嵌入，以使附近的节点在网络中靠在一起
  • 给定一个节点u，我们如何定义附近的节点？
    • NR（u）…通过某些策略R获得的u的邻域

优化特征学习

  • 给定G =（V，E），
  • 我们的目标是学习映射z：u→ℝ＆。
  • 对数似然目标：

其中NR（u）是策略R在节点u的附近

给定节点u，我们想学习可预测其邻域NR（u）中的节点的特征表示

  1. 使用某种策略R从图上的每个节点开始进行短的定长随机游动
  2. 对于每个收集到的NR（u）的节点，从u开始随机走访的节点的多集*
  3. 根据以下条件优化嵌入：给定节点u，预测其邻居NR（u）
  • 直觉：优化嵌入以最大化随机行走共生的可能性
  • 使用softmax参数化P（v | zu）：

总结：

优化随机游动嵌入= 查找最小化L的嵌入zu

但是天真地这样做太昂贵了！

来自softmax的归一化项是 罪魁祸首……我们能近似一下吗？

解决方案：负采样

而不是标准化w.r.t.所有节点，只需针对k个随机“负样本”进行归一化

  • 取样k个负节点与度成比例
  • 关于k（负样本数）的两个注意事项：
    • 1.较高的k给出更可靠的估计
    • 2.较高的k对应于负面事件的较高偏见

实际上k = 5-20

  1. 使用某种策略R从图上的每个节点开始进行短的定长随机游走。
  2. 对于您收集的每个节点NR（u），从u开始的随机游历中访问的节点的多集
  3. 使用随机梯度下降优化嵌入：

我们可以使用负采样有效地近似它！

如何随机游走？

  • 到目前为止，我们已经描述了在给定随机游动统计的情况下如何优化嵌入
  • 我们应该使用什么策略来进行这些随机游走？
    • 最简单的想法：只需从每个节点开始进行定长，无偏的随机游走（即Perozzi等人的DeepWalk等人，2013年）。
      • 问题是这种相似性概念太受约束
    • 我们如何概括这一点？

Node2Vec

  • 目标：具有相似网络邻居的嵌入节点在特征空间中关闭
  • 我们将此目标定为最大似然优化问题，与下游预测任务无关
  • 关键观察：节点u的网络邻域NR（u）的灵活概念导致丰富的节点嵌入
  • 开发有偏二阶随机游走R以生成节点u的网络邻域NR（u）

想法：使用灵活，有偏见的随机游走，可以在网络的本地视图和全局视图之间进行权衡（Grover和Leskovec，2016年）

广度优先和深度优先

  • 给定节点u的有偏定长随机游走R生成邻域NR（u）
    • 两个参数：
      • 返回参数p：
        • 返回上一个节点
      • 出入参数q：
        • 向外移动（DFS）与向内移动（BFS）
        • 从直觉上讲，q是BFS与DFS的“比率”

偏二阶随机游走探索网络邻域：

  • Rnd。刚走过的边（s1，w），现在在w
  • 见解：w的邻居只能是：

想法：记住步行的来源

行人越过边缘（sc，w）并在w处。接下来要去哪里？

  • p，q模型转移概率
    • p…返回参数
    • q…“走开”参数
  • 类似于BFS的游走：p的值低
  • 类似于DFS的游走：q的值低

node2vec 算法

  • 1）计算随机游走概率
  • 2）模拟从每个节点u开始的长度为l的r个随机游动
  • 3）使用随机梯度下降优化node2vec目标

线性时间复杂度 所有3个步骤均可单独并行化

  • 如何使用节点的嵌入zi：
    • 聚类/社区检测：聚类点zi
    • 节点分类：基于zi预测节点i的标签f（zi）
    • 链接预测：根据f（zi，zj）预测边缘（i，j）
      • 我们可以实现：连接，平均，乘积或在嵌入之间进行区别：
      • 级联：f（zi，zj）= g（[zi，zj]）
      • 哈达玛（Hadamard）：f（zi，zj）= g（zi ∗ zj）（每个坐标积）
      • 总和/平均值：f（zi，zj}）= g（zi + zj）
      • 距离：f（zi，zj）= g（|| zi − zj || 2）
  • 基本思想：嵌入节点，以便嵌入空间中的距离反映原始网络中的节点相似性。
  • 节点相似性的不同概念：
    • 基于邻接关系（即，如果连接则相似）
    • 多跳相似性定义
    • 随机游走方法
  • 那我应该用什么方法呢？
  • 在所有情况下，没有一种方法能胜出……。
    • 例如，node2vec在节点分类上表现更好，而多跳方法在链路预测上表现更好（Goyal和Ferrara，2017年调查）
  • 一般情况下，随机游走方法更有效
  • 通常：必须选择与您的应用程序匹配的节点相似性定义！

多关系数据建模的翻译嵌入

知识图谱

知识图是由有关的事实/陈述组成的相互关联的实体

节点称为实体，边称为关系

KG不完整会严重影响依赖它的系统的效率

直觉：我们想要一个链接预测模型，该模型可以从KG中的本地和全局连接模式中学习，同时考虑实体和不同类型的关系。

下游任务：通过使用学习的模式来概括感兴趣的实体与所有其他实体之间观察到的关系，可以进行关系预测。

翻译嵌入

  • 在TransE中，实体之间的关系表示为三元组
    • h（头实体），l（关系），t（尾部实体）=>（ℎ，l，t）
  • 首先将实体嵌入到实体空间Rk中
    • 与以前的方法类似
  • 关系表示为翻译
    • 如果给定事实为真 ℎ+ l≈t
    • 否则，ℎ+ l≠t

算法

整个图的嵌入

目标：要嵌入整个图形G

  • 任务：
    • 对有毒与无毒分子进行分类
    • 识别异常图

方法1

  • 简单的想法：
    • 在（子）图G上运行标准图嵌入技术
    • 然后，对（子）图G中的节点嵌入求和（获取平均值）

Duvenaud等人（2016年使用）根据分子的图结构对分子进行分类

方法2

  • 想法：引入一个“虚拟节点”来表示（子）图形并运行标准的图形嵌入技术

Li et al。，2016作为子图嵌入的通用技术提出

方法3

  • 匿名漫游中的状态对应于我们第一次随机游走访问节点的索引

Anonymous Walk Embeddings, ICML 2018 https://arxiv.org/pdf/1805.11921.pdf

随机游走数量的增长

  • 匿名漫游的数量呈指数增长：
    • 5个匿名随机游走长度为3的ai a1 = 111，a2 = 112，a3 = 121，a4 = 122，a5 = 123

匿名行走的思路1

  • 枚举l步中所有可能的匿名步行a1并记录其计数
  • 将图表表示为这些游历的概率分布
  • 例如：
    • 设置l = 3
    • 然后我们可以将图形表示为5维矢量
    • 由于有5条长度为3的匿名步行ai：111、112， 121、122、123
    • Zg [i] = G中匿名行走ai的概率

匿名行走思路2 取样

  • 在大图中完全计数所有匿名行走可能是不可行的
  • 逼近真实分布的抽样方法：独立生成一组m个随机游走并计算其对应的匿名游走的经验分布
  • 我们需要多少次随机游走？
    • 我们希望分布的误差大于概率 ϵ。小于σ ：

匿名行走思路3 学习行走嵌入

  • 了解每个匿名步行信息的嵌入zi
  • 那么图G的嵌入就是步行嵌入zi的 求和/平均/并置
  • 如何嵌入行走？
    • 注意：埋入式步道下次步行可以预测
    • 设置zi s.t.我们最大化

总结

我们讨论了3种想法来图形化嵌入

  • 方法1：嵌入节点并对它们求和/求平均值
  • 方法2：创建跨越（子）图的超节点，然后嵌入该节点
  • 方法3：匿名行走嵌入
    • 思路1：通过分布在所有匿名步行上来表示图
    • 思路2：对步行进行抽样以近似分布
    • 思路3：嵌入匿名步行
赞 (0)

相关推荐