2016 KDD
1 intro
- 利用graph上的节点相似性,对这些节点进行embedding
- 同质性:节点和其周围节点的embedding比较相似
- 蓝色节点和其周围的节点
- 结构等价性
- 结构相近的点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相似()
- 目标:最小化损失函数L
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 实验结果