建设企业管理类网站,中国电商平台有多少家,wordpress功能修改,北京欢迎你网站建设2016 KDD
1 intro
利用graph上的节点相似性#xff0c;对这些节点进行embedding 同质性#xff1a;节点和其周围节点的embedding比较相似 蓝色节点和其周围的节点结构等价性 结构相近的点embedding相近 比如蓝色节点#xff0c;都处于多个簇的连接处
2 随机游走
2.1 介绍…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的随机游走 会导致游走局部化或者仅在个别点之间游走——提出两个参数概率用来控制游走策略 从wt时刻到s1t1时刻 t1时刻和t-1时刻的距离为0——return parameter 从wt时刻到s2t1时刻 t1时刻和t-1时刻的距离为1 从wt时刻到s3t1时刻 t1时刻和t-1时刻的距离为2——walk away parameter
2.3.1 一次游走多个节点游走路径
在寻找随机游走的过程中我们可以通过一次游走深度优先遍历的算法路径长寻找出多个节点的游走路径路径短 2.3.2 pq对路径搜索的影响
DFS深度优先即q值小探索强。会捕获同质性节点即相邻节点表示类似。 BFS广度优先即p值小保守周围。会捕获结构性即某些节点的图上结构类类似。
2.3.3 随机游走算法优化
上述算法有一个问题就是我计算P(v|Zu)时分母还是需要每一对node 都计算一边那么还是的时间复杂度 解决方法负采样 分母改为随机采样k个点 每个点负采样概率正比于这个点的度数 3 用点embedding 表示边embedding
通过平均、哈达玛积元素相乘、L1、L2计算方式表示边的embedding 4 实验结果
