CS224W—03 GNN
CS224W—03 GNN
回顾
快速回顾一下上一讲的内容。我们学到的关键概念是节点嵌入(Node Embedding)。我们的直觉是将网络中的节点编码到低维向量空间中。我们希望学习一个接受输入图的函数 f f f,并将其嵌入到低维节点嵌入空间中。在这里,我们投影到二维。图机器学习的关键问题是如何定义这个函数 f f f。
我们如何对节点进行编码?目标是定义一个可以表示网络中相似性的相似函数,并在嵌入空间中进行近似。我们需要定义两件事:相似度函数 s i m i l a r i t y ( ⋅ ) similarity(\cdot) similarity(⋅) 和编码器函数 E N C ( ⋅ ) ENC(\cdot) ENC(⋅)。相似度函数表示网络中两个节点的接近程度,而编码器函数则告诉我们如何将图中的节点映射到嵌入空间。
我们如何定义相似度?上一讲中,我们讨论了基于随机游走的相似度函数。例如,假设两个节点在短随机游走中同时出现,那么我们认为这两个节点是相似的。
我们已经看到了对节点进行编码的最简单方法之一,即通过shallow-encoder查找。在这个浅层编码器中,我们有嵌入矩阵,嵌入矩阵的一列代表一个节点。嵌入矩阵的维数表示节点嵌入的大小。
然而,这种浅层编码器存在一些问题。
- 复杂度为 O ( ∣ V ∣ d ) O(|V|d) O(∣V∣d):首先,编码节点的方式并不是真正可扩展的,因为我们需要为每个节点分配一个可学习的向量。这将导致大量的参数,不适用于现实世界的大图。
- 这种方法是推导性的(transductive),只能应用于训练期间见过的节点。这意味着如果出现一个新节点,我们不知道如何编码该新节点,因为它甚至不在嵌入矩阵中。
- 没有包含节点特征。在现实世界的图中,属性或节点特征通常非常有价值。例如,在蛋白质相互作用图中,我们有很多可以与给定节点关联的蛋白质属性。如果没有这个属性,我们将无法从网络中进行有意义的学习。
本节中,我们将定义多层神经网络转换,并使用该深度神经网络对图中的节点进行编码,而不是使用嵌入查找。
假设我们有了这个编码器,我们能做什么呢?
- 节点分类(Node classfication)。例如,假设我们有一个药物蛋白质相互作用网络,然后我们可以预测这种药物是否有毒,或者是否可以用于治疗特定的疾病。
- 链接预测(Link prediction)。链接预测对于推荐系统来说非常有用,我们可以在其中定义用户和项目之间的交互网络。我们可以预测用户是否会购买某种商品。
- 社区检测(Community detection)。这对于金融网络来说非常有用,因为那里可能存在一群欺诈者,他们之间可能有一些可疑的交易。我们的目标是检测网络中的此类异常集群。
- 网络相似性(Network similarity)。在这种情况下,它将是图级任务或图级预测。例如,我们可以利用这个想法来编码不同的药物分子。所以在这里,我们将分子视为一个网络,我们想要对不同类型的分子进行分类。
Deep Learning for Graphs
Setup
有一个图 G G G:
-
V V V 是顶点集合
-
A A A 是邻接矩阵(假设为二进制)
-
X ∈ R ∣ V ∣ × m \mathbf{X}\in \R^{|V|\times m} X∈R∣V∣×m 为节点特征矩阵
-
v v v: V V V中的一个节点: N ( v ) N(v) N(v):节点 v v v的邻居集合。
-
节点特征:
-
社交网络:用户档案,用户图片
-
生物网络:基因表达谱,基因功能信息
-
当图中数据集没有节点特征时:
-
指示向量(节点的one-hot编码)
-
常数向量: [ 1 , 1 , … , 1 ] [1, 1, \ldots, 1] [1,1,…,1]
-
-
A Naive Approach
简单的想法:将邻接矩阵和特征合并在一起应用在深度神经网络上(如图,直接一个节点的邻接矩阵+特征合起来作为一个输入)。这种方法的问题在于:
- 需要 O ( ∣ V ∣ ) O(|V|) O(∣V∣) 的参数
- 不适用于不同大小的图
- 对节点顺序敏感。
排列不变性与同变性
利用image卷积的思想,扩展到graph上。现实世界的图上无法定义固定的locality或滑动窗口,而且图是permutation invariant的,没有规范的排列顺序。
- Permutation Invariant 用于全局图表示,确保输出与节点排列无关。
- Permutation Equivariant 用于节点级别表示,确保输出在节点排列变化时按相同方式变化。
Permutation Invariant(排列不变性):
排列不变性通常指的是模型对节点特征的排列顺序不敏感。这意味着无论节点特征的顺序如何变化,只要特征值本身保持不变,模型的输出也应该保持不变。
f ( A 1 , X 1 ) = f ( A 2 , X 2 ) f(A_1,X_1)=f(A_2,X_2) f(A1,X1)=f(A2,X2)
对于任意排列 P P P: f ( A , X ) = f ( P A P T , P X ) f(A,X)=f(PAP^T,PX) f(A,X)=f(PAPT,PX)
比如
f ( { 1 , 2 , 3 } ) = [ 1 , 2 , 3 ] f ( { 2 , 1 , 3 } ) = [ 1 , 2 , 3 ] f(\{1,2,3\})=[1,2,3]\\ f(\{2,1,3\})=[1,2,3] f({1,2,3})=[1,2,3]f({2,1,3})=[1,2,3]
Permutation Equivariant(排列同变性):
如果图的节点排列发生变化,那么模型的输出会按相同的方式重新排列。这在处理图中每个节点的表示(如节点分类任务)时非常重要。
对于任意排列 P P P: P f ( A , X ) = f ( P A P T , P X ) Pf(A,X)=f(PAP^T,PX) Pf(A,X)=f(PAPT,PX)
比如:
f ( { 1 , 2 , 3 } ) = [ 1 , 2 , 3 ] f ( { 2 , 1 , 3 } ) = [ 2 , 1 , 3 ] f(\{1,2,3\})=[1,2,3]\\ f(\{2,1,3\})=[2,1,3] f({1,2,3})=[1,2,3]f({2,1,3})=[2,1,3]
GCN
思想:基于节点的邻居定义一个计算图;通过学习图的传播信息来计算节点特征。
Aggregate Neighbors
核心思想:基于局部的网络邻居产生节点嵌入。
以上图为例,我们想要对节点A进行编码。我们将通过查找 A 在网络中的直接邻居 B、C 和 D 来获得计算图。然后我们将迭代地为其每个邻居计算邻居结构。因此,对于节点 B,我们将看到其邻居 A 和 C。对于节点 C,我们将看到其邻居ABEF,依此类推。这种展开可以迭代地发生,直到达到希望看到的轮数。这就是网络中的层数。
需要注意的事情是一个节点可以在此计算图中出现多次。
而这种深度模型就是有很多层
- 每个层的节点都有嵌入
- 第 k k k层嵌入获取来自 k k k跳距离节点的信息
如何聚合邻居的信息:平均邻居信息,然后应用神经网络
GCN: invariance and equivariance
给定一个节点,计算其embedding是置换不变的
如果考虑图中的所有节点,GCN的计算是置换同变的:
-
输入节点特征的行与输出嵌入的行对齐:
- 这意味着在输入特征矩阵中,每个节点的特征行与在输出嵌入矩阵中的相应行是一一对应的。换句话说,如果我们有一个节点特征矩阵,其中每一行代表一个节点的特征,那么在经过GCN处理后,输出嵌入矩阵中的每一行也将代表同一个节点的嵌入。
-
GCN计算给定节点的嵌入是不变的:
- 这意味着无论输入特征矩阵如何排列,只要节点的特征值不变,GCN计算出的该节点的嵌入也将保持不变。这是GCN排列不变性的表现。
-
排列后,给定节点在输入特征矩阵中的位置变了,但输出嵌入保持相同:
- 当输入特征矩阵的行(即节点特征)被重新排列后,该节点在矩阵中的位置会发生变化。然而,由于GCN的排列不变性,该节点的输出嵌入不会改变。这意味着无论输入特征的排列顺序如何,输出嵌入矩阵中相应节点的嵌入都将保持一致。
-
例如C和D的位置一样,节点特征一样,输入的位置不一样,那么输出的嵌入一样(排列不变性),位置不一样(排列同变性)。
模型训练
模型的参数定义如下:
我们可以将这些嵌入输入到任何损失函数中,并运行SGD来训练权重参数:
- h k h_k hk:节点 v v v在第 k k k层的隐藏表示
- W k W_k Wk:用于邻域聚合的权重矩阵
- B k B_k Bk:用于转换自身隐藏向量的权重矩阵
矩阵化
可以通过(稀疏)矩阵操作高效执行许多聚合:
- 隐藏嵌入矩阵 H ( k ) = [ h 1 ( k ) ⋯ h ∣ V ∣ ( k ) ] H^{(k)}=[h_1^{(k)}\cdots h_{|V|}^{(k)}] H(k)=[h1(k)⋯h∣V∣(k)]
- 然后: ∑ u ∈ N v h u ( k ) = A v , : H ( k ) \sum_{u\in N_v}h_u^{(k)}=A_{v,:}H^{(k)} ∑u∈Nvhu(k)=Av,:H(k)
- 设 D D D 为对角矩阵,其中 D v , u = deg ( v ) = ∣ N ( v ) ∣ D_{v,u} = \deg(v) = |N(v)| Dv,u=deg(v)=∣N(v)∣
- D D D 的逆矩阵 D − 1 D^{-1} D−1 也是对角的: D v , u − 1 = 1 / ∣ N ( v ) ∣ D_{v,u}^{-1} = 1/|N(v)| Dv,u−1=1/∣N(v)∣
- 因此,
参数更新函数可以重写如下:
当aggregation函数过度复杂时,GNN可能无法被表示成矩阵形式。
训练
节点嵌入 z u \mathbf{z}_u zu是输入图的函数。
监督设置:我们希望最小化损失 min Θ L ( y , f ( z u ) ) \underset\Theta\min \mathcal{L}(\mathbf{y}, f(\mathbf{z}_u)) ΘminL(y,f(zu)):
- y \mathbf{y} y:节点标签
- 如果 y \mathbf{y} y 是实数, L \mathcal{L} L可以是 L 2 L2 L2损失;如果 y \mathbf{y} y 是分类标签,可以是交叉熵损失,。
- 对于节点分类,可以设计如下损失函数:
无监督设置:
- 没有节点标签可用
- 使用图结构作为学习的目标。
- min Θ L = ∑ z u , z v CE ( y u , v , DEC ( z u , z v ) ) \min _{\boldsymbol{\Theta}} \mathcal{L}=\sum_{z_u, z_v} \operatorname{CE}\left(y_{u, v}, \operatorname{DEC}(z_u,z_v)\right) minΘL=∑zu,zvCE(yu,v,DEC(zu,zv))
- 其实如果u和v相似,则 y u , v = 1 y_{u,v}=1 yu,v=1
- z u = f Θ ( u ) z_u=f_{\Theta}(u) zu=fΘ(u), D E C ( ⋅ ) DEC(\cdot) DEC(⋅) 为点积。
- CE ( y , f ( x ) ) = − ∑ i = 1 C ( y i log f Θ ( x ) i ) ) \operatorname{CE}(\boldsymbol{y}, f(\boldsymbol{x}))=-\sum_{i=1}^C\left(y_i \log f_{\Theta}(x)_i\right)) CE(y,f(x))=−∑i=1C(yilogfΘ(x)i))
- 节点的相似性可以使用上一节学习的随机游走以及矩阵分解来求得。
模型设计
模型设计:
- 定义邻居聚合函数
- 定义节点嵌入上的损失函数
- 在节点集合(如计算图的batch)上做训练
- 训练后的模型可以应用在训练过与没有训练过的节点上
推导能力
相同的聚合参数被所有节点共享:模型参数的数量与节点数 N N N成次线性关系,我们可以推广到未见过的节点。
参考资料
- http://t.csdnimg.cn/Hvhhx
- https://web.stanford.edu/class/cs224w/
相关文章:

CS224W—03 GNN
CS224W—03 GNN 回顾 快速回顾一下上一讲的内容。我们学到的关键概念是节点嵌入(Node Embedding)。我们的直觉是将网络中的节点编码到低维向量空间中。我们希望学习一个接受输入图的函数 f f f,并将其嵌入到低维节点嵌入空间中。在这里&am…...

库存超卖问题解决方式
文章目录 超卖问题解决方式什么是库存超卖问题?乐观锁和悲观锁的定义超卖问题解决方式一、悲观锁1.jvm单机锁2.通过使用mysql的行锁,使用一个sql解决并发访问问题3.使用mysql的悲观锁解决4. 使用redis分布式锁来解决 二、乐观锁解决1.版本号2. CAS法&…...

30岁决心转行,AI太香了
今天是一篇老学员的经历分享,此时的王同学在大洋彼岸即将毕业,手握多家北美大厂offer,一片明媚。谁能想到王同学的转码之路竟始于一场裁员,这场访谈拉开了他的回忆。 最近总刷到一些关于转行的话题,很多刚毕业的同学喜…...

C#知识|文件与目录操作:目录的操作
哈喽,你好啊,我是雷工! 前边学习了文件的删除、复制、移动,接下来学习目录的操作。 以下为学习笔记。 01 效果演示 1.1、显示指定目录下的所有文件 在左侧的文本框中显示出F:\F004-C#目录下的所有文件, 演示效果: 1.2、显示指定目录下的所有子文件 在左侧的文本框中显…...

从零到一:用Go语言构建你的第一个Web服务
使用Go语言从零开始搭建一个Web服务,包括环境搭建、路由处理、中间件使用、JSON和表单数据处理等关键步骤,提供丰富的代码示例。 关注TechLead,复旦博士,分享云服务领域全维度开发技术。拥有10年互联网服务架构、AI产品研发经验、…...

塔子哥的环游之旅-腾讯2023笔试(codefun2000)
题目链接 塔子哥的环游之旅-腾讯2023笔试(codefun2000) 题目内容 塔子哥是一位热衷旅游的程序员。他所在的国家共有 n 个城市,编号从 1 到 n。这些城市之间有 m 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 1 的城市,他计划前往编号为 n 的城市进行旅游…...

力扣SQL50 换座位
Problem: 626. 换座位 👨🏫 参考题解 Code SELECT(CASEWHEN MOD(id, 2) ! 0 AND counts ! id THEN id 1WHEN MOD(id, 2) ! 0 AND counts id THEN idELSE id - 1END) AS id,student FROMseat,(SELECTCOUNT(*) AS countsFROMseat) AS seat_counts O…...

SOPHGO算能科技BM1684芯片修改内存布局
目录 1 问题由来 2 下载memory_edit工具 3 查看当前内存配置 3 修改内存布局 4 替换生效 参考文献: 1 问题由来 我在算能SE5盒子上开发的时候,明显感觉很慢,然后看了下cpu内存竟然只有2.6G 但是这个盒子出厂默认是12G的,于…...
CUDA实现矩阵乘法的性能优化策略
本人主要参考了https://zhuanlan.zhihu.com/p/435908830,https://zhuanlan.zhihu.com/p/410278370,https://zhuanlan.zhihu.com/p/518857175 ,下面的代码均是本人实现 矩阵乘法的easy实现-V1 C = A B , A ∈ R M K , B ∈ R K...
element ui 修改table筛选按钮为自定义按钮
element ui 修改table筛选按钮为自定义按钮 前些时间做项目的时候,有个需求是,嫌elementui 自定的筛选按钮 下拉的小三角不好看,需要自定义按钮。 具体的实现方法如下: 从阿里的图片库引入自己想要的图标。在需要修改按钮的vue页…...
面向对象编程:一切皆对象
面向对象(OOP)是一种编程范式,它使用对象来设计软件。对象可以包含数据和代码:数据代表对象的状态,而代码代表操作数据的方式。在面向对象编程中,一切皆对象,这意味着将现实世界事务使用类与实例来模拟,如灯࿰…...

GIT版本管理与分支控制
目录 1、了解Git功能 2、第一次使用Git(首次配置好,后续不用再操作) 打开git后端 设置用户签名 结果 3、初始项目架构 创建本地新仓库并初始化 文件添加到本地仓库 a.文件添加缓存区 b.缓存区内容提交到本地仓库 c.改写提交的注释 …...

大模型算法备案流程最详细说明【流程+附件】
文章目录 一、语料安全评估 二、黑盒测试 三、模型安全措施评估 四、性能评估 五、性能评估 六、安全性评估 七、可解释性评估 八、法律和合规性评估 九、应急管理措施 十、材料准备 十一、【线下流程】大模型备案线下详细步骤说明 十二、【线上流程】算法备案填报…...
JAVA GUI 基本使用
package com.lu.gui;import javax.swing.*; import java.awt.*;public class MyJFrame extends JFrame {public MyJFrame() {this.setBackground(Color.BLACK);this.setResizable(false);this.setSize(500,500);this.setTitle("登录页面");} }package com.lu.gui;imp…...

【涵子来信】——AI革新:1.新时代是便捷的,要会用
各位读者朋友们: 我们现在AI时代的十字路口,AI是为生活带来便利的,我们要会使用AI。今天这篇文章来讲述一下AI的正确使用。 一、 AI的使用 1.1.便捷之中要会辨别 AI是带来强大的,利用好可以给生活带来便捷。 像之前WWDC24宣传…...

自定义线程池实现(一)
预期目标 1.实现一个相对完备的线程池 2.自定义拒绝策略(下一节) 线程池的基本参数 1.核心线程数 2.超时时间 3.拒绝策略(在下一篇中添加) 4.工作队列 5.任务队列 工作机制 当添加一个任务到线程池中时,线程池会…...

计算机毕业设计选题推荐-零食批发商仓库管理系统-Java/Python项目实战
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...

基于springboot+vue+uniapp的校园快递平台小程序
开发语言:Java框架:springbootuniappJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包&#…...

这两个大龄程序员,打算搞垮一个世界软件巨头!
大家都知道,Adobe是多媒体和数字内容创作者的绝对王者,它的旗下有众多大家耳熟能详的软件:Photoshop、Illustrator、Premiere Pro、After Effects、InDegign、Acrobat、Animate等等。 这些软件使用门槛很高,价格昂贵,安…...

LabVIEW放大器自动测量系统
开发了一个基于LabVIEW平台的多路前置放大器自动测量系统的开发与实施。该系统集成了硬件控制与软件编程,能够实现放大器各项性能指标的快速自动测量,有效提高了测试的精确性和效率。系统设计采用了虚拟仪器技术,结合了先进的测量与控制策略&…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...

实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...