机器学习笔记:node2vec(论文笔记:node2vec: Scalable Feature Learning for Networks)

2016 KDD

1 intro

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

2 随机游走

2.1 介绍

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

2.2 具体算法

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

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 都计算一边,那么还是O(|V|^2)的时间复杂度

解决方法:负采样

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

3 用点embedding 表示边embedding

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

4 实验结果

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/122815.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

『C语言进阶』指针进阶(一)

🔥博客主页: 小羊失眠啦 🔖系列专栏: C语言 🌥️每日语录:无论你怎么选,都难免会有遗憾。 ❤️感谢大家点赞👍收藏⭐评论✍️ 前言 在C语言初阶中,我们对指针有了一定的…

《机器人学一(Robotics(1))》_台大林沛群 第 5 周【机械手臂 轨迹规划】 Quiz 5

我又行了!🤣 求解的 位置 可能会有 变动,根据求得的A填写相应值即可。注意看题目。 coursera链接 文章目录 第1题 Cartesian space求解 题1-3 的 Python 代码 第2题第3题第4题 Joint space求解 题4-6 的 Python 代码 第5题第6题其它可参考代…

编写软件检测报告有哪些注意事项?软件检测报告获取

软件检测报告是指把测试的过程和结果写成文档,对发现的问题和缺陷进行分析,为纠正软件的存在的质量问题提供依据,同时为软件验收和交付打下基础。 一、编写软件检测报告的注意事项 1、报告的结构要合理和清晰。应该按照一定的逻辑顺序&…

解决 Spring Boot 与 springfox 的 NullPointerException 问题

🌷🍁 博主猫头虎(🐅🐾)带您 Go to New World✨🍁 🦄 博客首页——🐅🐾猫头虎的博客🎐 🐳 《面试题大全专栏》 🦕 文章图文…

MySQL误删数据 回滚

前言 生产环境数据库不允许删除表,可以将表修改成 XXX_to_delete 如果误删简单数据,可以考虑使用binlog恢复 一、查看命令 1.查看binlog是否开启 show variables like log_bin;切换到MySQL安装目录,查看mysqlbinlog日志文件 2.查看所有 binlog 日志…

Ansible学习笔记12

playbook: playbook(剧本):是ansible用于配置、部署和管理被控节点的剧本,用于Ansible操作的编排。 使用的是yaml格式,(saltstack、elk、docker、docker-compose、k8s都会使用到yaml格式。&am…

【c++ debug】cmake编译报错 No such file or directory

1. 报错:error while loading shared libraries: libprotoc.so.24: cannot open shared object file: No such file or directory 问题原因:找不到动态库 解决方法:添加动态库路径 export LD_LIBRARY_PATH$LD_LIBRARY_PATH:/your/protobuf/l…

【C语言】入门——结构体

目录 结构体 为什么有结构体? 1.结构体的声明 1.2结构体变量的访问和初始化 2.结构体成员的访问 结构体 struct 结构体类型 {//相关属性; }结构体变量; 结构体和数组不同,同一类型的数据的集合是数组; 结构体是多种类型的数据的集合&…

【Java Web】统一处理异常

一个异常处理的ControllerAdvice类。它用于处理Controller注解的控制器中发生的异常。 具体代码功能如下: 导入相关类和方法。声明一个Logger对象,用于日志记录。使用ExceptionHandler注解标记handleException方法,用于处理所有异常。 -嘛在…

C++——shared_ptr:make_shared的用处,与shared_ptr直接构造的区别

shared_ptr shared_ptr继承自__shared_ptr,其中有两个对象,一个是指向资源的指针,一个是控制块,指向一个引用计数对象。控制块中存储了强引用和弱引用的计数,强引用Uses代表shared_ptr对象的引用计数,弱引…

每日一题 1921. 消灭怪物的最大数量

难度:中等 思路: 已知速度和距离,可求时间必定先消灭时间最短的怪物求得时间数组排序,只要在第 i 秒时,time[i] > i ,那么就可以消灭第 i 个怪物 代码: class Solution:def eliminateMax…

Leetcode刷题笔记--Hot41-50

1--二叉树的层序遍历(102) 主要思路: 经典广度优先搜索,基于队列; 对于本题需要将同一层的节点放在一个数组中,因此遍历的时候需要用一个变量 nums 来记录当前层的节点数,即 nums 等于队列元素的…

存储过程报Illegal mix of collations错误的解决方法

CREATE PROCEDURE maxAgeStudent(IN _gender CHAR) BEGINDECLARE maxage INT DEFAULT 0;SELECT max(age) INTO maxage FROM student where gender _gender;SELECT * from student WHERE age maxage and gender _gender; END; 在调用的时候 call maxAgeStudent(1) 产生了报…

Linux之DNS域名解析服务

目录 Linux之DNS域名解析服务 概述 产生原因 作用 连接方式 因特网的域名结构 拓扑 分类 域名服务器类型 ​编辑 DNS域名解析过程 分类 解析图 搭建DNS域名解析服务器 概述 安装软件 bind服务中三个关键文件 主配置文件分析 一般需要修改三部分:…

核辐射检测仪电子测量方案

核辐射检测仪又名辐射检测仪,主要是安检、海关、实验室、金属探测公司等行业使用。但由于2023年8月24日排放核废水,导致海洋遭受核辐射污染,由于大海的净化能力有限,则会导致核废水有可能随着洋流的运动,会流至我国海域…

Python列表排序

介绍一个关于列表排序的sort方法,看下面的案例: """ 列表的sort方法来对列表进行自定义排序 """# 准备列表 my_list [["a", 33], ["b", 55], ["c", 11]]# 排序,基于带名函数 …

依赖导入失败场景和解决方案

在使用 Maven 构建项目时,可能会发生依赖项下载错误的情况,主要原因有以下几种: 下载依赖时出现网络故障或仓库服务器宕机等原因,导致无法连接至 Maven 仓库,从而无法下载依赖。 依赖项的版本号或配置文件中的版本号错…

c语言练习41:深入理解字符串函数strlen strcpy strcat

深入理解字符串函数strlen strcpy strcat 模拟实现&#xff1a;”strlen strcpy strcat strlen strcat: #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<assert.h> strlen 1.通过指针移动模拟 //int my_strlen(char* str) { // size_t c…

MySQL 枚举类型如何定义比较好 tinyint?enum?varchar?

enum介绍 先来介绍一下enum类型吧。 ENUM 是一个字符串对象&#xff0c;其值通常选自一个允许值列表中&#xff0c;该列表在表创建时的列规格说明中被明确地列举。&#xff08;建表的时候写到建表语句里&#xff09; 虽然表面是字符串值&#xff0c;但其内部是数字索引&…

Docker私有镜像仓库(Harbor)安装

Docker私有镜像仓库(Harbor)安装 1、什么是Harbor Harbor是类似与DockerHub 一样的镜像仓库。Harbor是由VMware公司开源的企业级的Docker Registry管理项目&#xff0c;它包括权限管理(RBAC)、LDAP、日志审核、管理界面、自我注册、镜像复制和中文支持等功能。Docker容器应用的…