2016 KDD

1 intro

• 利用graph上的节点相似性，对这些节点进行embedding
  • 同质性：节点和其周围节点的embedding比较相似
    • 蓝色节点和其周围的节点
    • 
  • 结构等价性
    • 结构相近的点embedding相近
      • 比如蓝色节点，都处于多个簇的连接处
      • 

2 随机游走

2.1 介绍

• 随机游走是一种自监督学习的embedding方法，不需要利用节点标签也不需要节点的特征，训练出来的embedding也不依赖于任何的特定任务
• 首先随机选择一个邻居节点，走到该处再随机选择一个邻居，重复length次
  • length是指随机游走的长度
  • 使用随机游走从起始节点到终止节点的概率值，实际上就可以用来表示相似度
    • 也就是说，从u到v节点的概率值，应该正比于u与v节点embedding之后的点乘结果
    • 
      • 

2.2 具体算法

• 根据某种策略R，从图上的每个点，执行一些随机游走
• 对图上的每个点u，收集相对应的点集
  • 是从u点出来的各条随机游走路径上的点集
  • 中可能会有重复的元素 
• 根据对数概率，优化embedding
  • 
  • 
  • 目标：最小化损失函数L
    • ——>最大化在中的v与u之间的log(P(v|Zu))
    • ——>最大化在u随机游走路径上的v与u之间的P(v|Zu)
      ——>在u随机游走路径上的v，尽量地和u相似（)
• 

2.3 随机游走策略

• 最简单的策略：从每个点跑固定长度，没有bias的随机游走
  • 会导致游走局部化或者仅在个别点之间游走
  • ——>提出两个参数（概率）用来控制游走策略

• 从w（t时刻）到s1（t+1时刻）

  • t+1时刻和t-1时刻的距离为0——return parameter

• 从w（t时刻）到s2（t+1时刻）

  • t+1时刻和t-1时刻的距离为1

• 从w（t时刻）到s3（t+1时刻）

  • t+1时刻和t-1时刻的距离为2——>walk away parameter

2.3.1 一次游走，多个节点游走路径

在寻找随机游走的过程中，我们可以通过一次游走（深度优先遍历的算法，路径长），寻找出多个节点的游走路径（路径短）

2.3.2 p，q对路径搜索的影响

• DFS，深度优先，即q值小，探索强。会捕获同质性节点，即相邻节点表示类似。
  • 
• BFS，广度优先，即p值小，保守周围。会捕获结构性，即某些节点的图上结构类类似。
  • 

2.3.3 随机游走算法优化

上述算法有一个问题，就是我计算P(v|Zu)时，分母还是需要每一对node 都计算一边，那么还是的时间复杂度

解决方法：负采样

•   分母改为随机采样k个点
  • 每个点负采样概率正比于这个点的度数
  • 

3 用点embedding 表示边embedding

通过平均、哈达玛积（元素相乘）、L1、L2计算方式表示边的embedding

4 实验结果