【补充】图神经网络前传——Node2vec

2024-05-13 18:44

本文主要是介绍【补充】图神经网络前传——Node2vec,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Node2Vec【图神经网络论文精读】_哔哩哔哩_bilibili

解决的问题:图嵌入

把每一个节点编码成一个d维的低维、稠密(不是one-hot)、连续(不是离散的,是实数->有助于保存更多的信息)向量,并且,这个向量应该包含原来节点的一些信息,特别是语义信息,同时还有结构信息、社群信息、邻域信息。

embedding之后,就可以正常ML了。 

不仅仅节点可以做embedding。这里的node2vec是对节点做embedding。

手工构造的特征有很好的可解释性,但是不一定是很好的特征。node2vec和deepwalk都是基于随机游走的方法。

deepwalk只能把相邻或者相近的点聚在一起,但是其他的不可以,比如苏伊士运河和巴拿马运河的功能类似,但是离得远,就没办法放在一起。

而对于node2vec,这里的随机游走就不再是完全的随机游走了,而是有偏随机游走。上图中,我们是从节点t走到了节点v,现在,我们要决定下一步向哪里走,这个时候我们有三个选择,返回(t节点),绕圈,走出去(离t更远了)。通过调整p q参数,来影响下一步往哪儿走。

(弹幕:这个功能相似性直观上好像是有偏游走的概率分布的相似性体现的)

不同的搜索策略会捕捉节点的不同特征。

这里的随机游走时2阶随机游走,而不是deepwalk中的1阶。在deepwalk中,下一个节点的采样仅取决于当前点的位置,而在node2vec中下一个节点不仅取决于当前节点,还要取决于上一个节点。->二阶随机游走/二阶马尔可夫

deepwalk可以看作是node2vec在p=1,q=1情况下的特例->可以通过调整p q值

优缺点

第二个优点纠正:节点分类->embedding

Node2Vec论文逐句精读_哔哩哔哩_bilibili

(这里并不是完全的笔记,仅包含自己翻译的部分和视频中觉得有必要记下来的部分)

可扩展的图嵌入表示学习算法->可扩展:可以用在整个互联网规模的图上,并且可以用有限的时间、空间的成本。

解决的是图嵌入问题,是把图中的节点编码、映射成一个低维、连续、稠密的向量,而这个向量反应了这个节点在原图中的连接、社群、结构、角色等语义特征。

表示学习:用ML方法(数据驱动的方法)做的映射,而非人工构造特征,也不是矩阵分解的方法。

abstract

对于网络中的节点和边来做预测,首先需要做特征工程,把他们变成向量,有了这些向量之后才能输入到后续的机器学习算法当中,继续做下游的预测、分类任务。但是当时表示学习(ML)在图中的应用(如deepwalk、line)的表示能力不够高->无法反应出节点更丰富的特征和更丰富的连接属性。

提出node2vec,一个更好的做node embedding的方法。

node2vec是使用极大似然估计来实现训练。定义了一个非常灵活的,有偏随机游走方法,可以有效的探索多样的属性(邻居?),得到更丰富的表示。

introduction

任何监督ML都需要内涵丰富语义、有分类区分行、相互独立的特征。对于网络(图)而言,我们需要先把节点和边表示成特征向量(用特征向量表示节点和边)。 

有监督的,针对特定任务的->找到针对下游任务的特征

无监督->通用的,与下游任务无关的特征

同一社群&同一功能角色的点应该具有相近的embedding

node2vec—>一种对于网络中可扩展的特征的半监督学习方法

二阶随机游走 

feature learning framework

给定网络G=(V, E),我们的目标是学习一个映射f: \ V \rightarrow \mathbb{R}^d,把每一个节点映射成一个d维的实数向量f是一个大小为|V| \times d的矩阵(就是一张表格,每个节点对应的d维的嵌入)。

对于每一个节点u \in V,我们定义N_s(u) \subset V为节点u通过邻居采样策略(neighborhood sampling strategy)S产生的网络邻居(network neighborhood)

(讲人话就是这个N表示的是通过策略S得到的邻居)

 

同样采用skip-gram方法,用中间节点去预测周围节点,让红框中的值最大化

为了简化问题,这里做了两个基本假设:

  1. 条件独立。假设观察到一个邻居节点与观察到任意其他邻居节点之间是独立的(周围节点互不影响)

    因此上面的红框可以简化成连乘的形式
    softmax计算方法⬆️
  2. 特征空间对称性。一个节点与其邻居节点对彼此的印象是对称的(两个节点之间相互影响的程度是一样的)。

怎么知道谁是邻居:

idea1:搜索

真实的图是两种策略的mix

BFS提供的是一种微观视角,采样出来方差小,而DFS是宏观视角,采样出来方差大(就难以表达局部特征)

(弹幕:其实按照up主举的皇帝和运河的例子可以看出,确实DFS是找宏观的同质性。而BFS只关注微观邻近的结构。)

->设计一个灵活的邻域采样策略,让我们能够平滑的在BFS和DFS之间插值(私以为就是类似通过调整参数控制l1, l2)

首先定义随机游走:

起始节点为u,上一个节点为t,当前节点为v,下一个节点为x

现在我们已经在v节点了,在此情况下,我们要去下一个节点x。若v和x之间没有连接,就是0,如果是有连接的话,就按照某个概率给每个连接赋予权重。上图中\pi是权重,下面的Z是归一化常量。

接下来就是确定p q。

idea:用连接的权重作为游走的概率->如果是带权重的图,那么就可以直接用权重作为概率,即:\pi_{vx} = w_{vx},如果是无权图,那就是w_{vx} = 1

这样久和deepwalk一样没办法调节游走策略

idea:直接用BFS或者DFS->太极端了  

->提出一个二阶随机游走策略

使用两个参数p,q来引导游走。

假设我们刚刚穿过边(t,v),现在驻足在节点v上,现在我们需要决定下一步。->边(v,x)的转移概率,我们将未归一化的转移概率定义为\pi_{vx} = \alpha_{pq}(t,x)\cdot w_{vx},其中:

\alpha_{pq}(t,x) = \left\{\begin{matrix} \frac{1}{p} & if \ d_{tx} = 0\\ 1 & if \ d_{tx} = 1\\ \frac{1}{q} & if \ d_{tx} = 2 \end{matrix}\right.

这里d_{tx}表示的是节点t和x之间的最短路径长度,且d_{tx}只能在\left \{ 0, 1, 2 \right \}中选一个。

p:return parameter->如果p很大,就不太可能在接下来的两步中再次采样已经经过的节点,如果p小,就会返回

q:in-out parameter->如果q很大,就会困在原地,如果q很小,就更倾向于远走高飞

注意:这里和起始节点无关,仅仅由当前节点和上一个节点决定下一个节点去哪儿。

node-embedding->link-embedding

判断两个点之间是否会存在连接

论文链接:

https://cs.stanford.edu/people/jure/pubs/node2vec-kdd16.pdf

这篇关于【补充】图神经网络前传——Node2vec的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/986516

相关文章

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}

【多系统萎缩患者必看】✨维生素补充全攻略,守护你的健康每一天!

亲爱的朋友们,今天我们要聊一个既重要又容易被忽视的话题——‌多系统萎缩患者如何科学补充维生素‌!🌟 在这个快节奏的生活中,健康成为了我们最宝贵的财富,而对于多系统萎缩(MSA)的患者来说,合理的营养补充更是维护身体机能、提升生活质量的关键一步。👇 🌈 为什么多系统萎缩患者需要特别关注维生素? 多系统萎缩是一种罕见且复杂的神经系统疾病,它影响身体的多个系统,包括自主神经、锥体外系、小脑及锥

机器学习之监督学习(三)神经网络

机器学习之监督学习(三)神经网络基础 0. 文章传送1. 深度学习 Deep Learning深度学习的关键特点深度学习VS传统机器学习 2. 生物神经网络 Biological Neural Network3. 神经网络模型基本结构模块一:TensorFlow搭建神经网络 4. 反向传播梯度下降 Back Propagation Gradient Descent模块二:激活函数 activ

Vue2电商项目(二) Home模块的开发;(还需要补充js节流和防抖的回顾链接)

文章目录 一、Home模块拆分1. 三级联动组件TypeNav2. 其余组件 二、发送请求的准备工作1. axios的二次封装2. 统一管理接口API----跨域3. nprogress进度条 三、 vuex模块开发四、TypeNav三级联动组件开发1. 动态展示三级联动数据2. 三级联动 动态背景(1)、方式一:CSS样式(2)、方式二:JS 3. 控制二三级数据隐藏与显示--绑定styl

图神经网络框架DGL实现Graph Attention Network (GAT)笔记

参考列表: [1]深入理解图注意力机制 [2]DGL官方学习教程一 ——基础操作&消息传递 [3]Cora数据集介绍+python读取 一、DGL实现GAT分类机器学习论文 程序摘自[1],该程序实现了利用图神经网络框架——DGL,实现图注意网络(GAT)。应用demo为对机器学习论文数据集——Cora,对论文所属类别进行分类。(下图摘自[3]) 1. 程序 Ubuntu:18.04

基于深度学习 卷积神经网络resnext50的中医舌苔分类系统

项目概述 本项目旨在通过深度学习技术,特别是利用卷积神经网络(Convolutional Neural Networks, CNNs)中的ResNeXt50架构,实现对中医舌象图像的自动分类。该系统不仅能够识别不同的舌苔类型,还能够在PyQt5框架下提供一个直观的图形用户界面(GUI),使得医生或患者能够方便地上传舌象照片并获取分析结果。 技术栈 深度学习框架:采用PyTorch或其他

图神经网络(2)预备知识

1. 图的基本概念         对于接触过数据结构和算法的读者来说,图并不是一个陌生的概念。一个图由一些顶点也称为节点和连接这些顶点的边组成。给定一个图G=(V,E),  其 中V={V1,V2,…,Vn}  是一个具有 n 个顶点的集合。 1.1邻接矩阵         我们用邻接矩阵A∈Rn×n表示顶点之间的连接关系。 如果顶点 vi和vj之间有连接,就表示(vi,vj)  组成了

自然语言处理系列六十三》神经网络算法》LSTM长短期记忆神经网络算法

注:此文章内容均节选自充电了么创始人,CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》(人工智能科学与技术丛书)【陈敬雷编著】【清华大学出版社】 文章目录 自然语言处理系列六十三神经网络算法》LSTM长短期记忆神经网络算法Seq2Seq端到端神经网络算法 总结 自然语言处理系列六十三 神经网络算法》LSTM长短期记忆神经网络算法 长短期记忆网络(LSTM,Long S

神经网络训练不起来怎么办(零)| General Guidance

摘要:模型性能不理想时,如何判断 Model Bias, Optimization, Overfitting 等问题,并以此着手优化模型。在这个分析过程中,我们可以对Function Set,模型弹性有直观的理解。关键词:模型性能,Model Bias, Optimization, Overfitting。 零,领域背景 如果我们的模型表现较差,那么我们往往需要根据 Training l

如何将卷积神经网络(CNN)应用于医学图像分析:从分类到分割和检测的实用指南

引言 在现代医疗领域,医学图像已经成为疾病诊断和治疗规划的重要工具。医学图像的类型繁多,包括但不限于X射线、CT(计算机断层扫描)、MRI(磁共振成像)和超声图像。这些图像提供了对身体内部结构的详细视图,有助于医生在进行准确诊断和制定个性化治疗方案时获取关键的信息。 1. 医学图像分析的挑战 医学图像分析面临诸多挑战,其中包括: 图像数据的复杂性:医学图像通常具有高维度和复杂的结构