如何理解图神经网络的傅里叶变换和图卷积
图神经网络(GNN)代表了一类强大的深度神经网络架构。在一个日益互联的世界里,因为信息的联通性,大部分的信息可以被建模为图。例如,化合物中的原子是节点,它们之间的键是边。
图神经网络的美妙之处在于它们能够在不牺牲重要细节的情况下直接对图结构数据进行操作。这一点在处理复杂的数据集(如化合物)时尤为明显,GNN使我们能够充分利用底层图形表示的丰富性。通过这样做,GNN能够更全面地理解原子和键之间的关系,从而为更准确和深入的分析开辟途径。
在化学领域之外,图结构的影响延伸到不同的领域。以交通数据为例,其中城市是节点,它们之间的路线是边。GNN在交通堵塞预测等任务中被证明是非常宝贵的,证明了它们在捕捉城市流动性的复杂动态方面是有效的。当面临预测交通拥堵等挑战时,GNN掌握图数据中固有的空间依赖性和模式的能力成为一种强有力的工具。基于GNN的众多模型已成为预测交通拥堵的最先进解决方案,成为最前沿的模型。下面是paperswithcode上预测交通堵塞的模型,基本上全部是GNN本文将介绍图卷积的理论基础。通过深入研究图傅立叶变换的复杂性及其与图卷积的联系,我们将为深入理解GNN世界中的这一关键概念奠定基础。
如何定义图卷积
GNN的核心概念在于图卷积,通过捕获节点和边之间的关系,实现对图数据的有效处理。在理解图卷积的各种方法中,本文侧重于利用图傅里叶变换的理论来进行解释。这个概念提供了一个深入研究图卷积的机制的独特视角。图傅里叶变换允许我们用图形频率来表示图形信号——与节点相关的数据。这种以光谱分析为基础的分解,提供了对图中潜在模式和结构的洞察。一些GNN架构利用注意力机制和其他超越图卷积范围的高级方法。但是我们主要探讨图卷积的本质及其与图傅立叶变换的相互作用,所以注意力等部分不在本文的范围内
什么是图傅里叶变换?
图傅里叶变换的概念与经典的傅里叶变换有着有趣的相似之处。就像传统的傅里叶变换将一个波信号分解成它的组成频率一样,图傅里叶变换在图结构数据进行操作,揭示嵌入其中的信号的频率。想象一个没有环路或多个边缘结构的加权无向图。图傅里叶变换是一种数学运算,它强调了图上存在的信号的变换。在信号维数等于1的情况下,这个概念变得特别具有说明性。考虑下面的描述,它描绘了信号在图表上的样子[1]。将信号分解为图的频率,或图傅里叶变换,提供了一种识别图形数据中固有的各种关系、规律和复杂性的方法。
图拉普拉斯算子
为了理解图的傅里叶变换,我们将开始一个基本的探索,首先介绍图的拉普拉斯变换。这个关键概念是揭示图形固有频率特性的基石。图拉普拉斯量记为L,定义为:在这个等式中,A表示邻接矩阵,它编码了图中节点之间的连接,D表示度矩阵,捕获每个节点的度。由于D和A是实对称矩阵,因此图拉普拉斯矩阵也具有实对称矩阵的性质。这个性质使我们能够对图拉普拉斯函数进行谱分解,表示为:
上式中,U表示特征向量矩阵,Λ是由特征值(Λ 1, Λ 2,…,Λ n)组成的对角矩阵。
二次形
本节解释了拉普拉斯图的二次形和二次形的含义,以及它如何与图信号的频率联系起来。图拉普拉斯的二次型可以定义为:这里的f表示图信号,w表示一条边的权值,Nk表示与节点k相连的节点集。这个表示形式揭示了两个基本的关键方面:函数的平滑性二次型提供了对函数在图形上的平滑性的洞察。考虑f =[1,1,1,…,1]T的场景。根据图拉普拉斯式的定义,二次型的计算结果为零。也就是说,函数在节点间越平滑,得到的二次型就越小。这种相互作用提供了一种机制来量化图形信号固有的平滑程度。相邻节点之间的相似性二次型也用作评估相邻节点上信号之间相似性的度量。当f(i)与f(j)相差较大时,对应的二次型值成比例增大。相反,如果相邻节点上的信号相似,则二次型趋近于零。这种观察结果与二次型值越大反映相邻节点之间变化越大的想法是一致的。有了这些概念,二次型就可以被解释为图形上函数“频率”的替代物。通过利用它提供信息,我们可以进行基于频率成分的图形信号分解。这一关键步骤是图傅里叶变换的先驱,解锁了一种强大的方法来揭示嵌入在图结构数据中的频率特征。
图傅里叶变换
我们已经建立了拉普拉斯图的二次形作为信号频率的指示器,其中二次形值越大表示频率越高。还有一个要点是:要注意这些值可能受到f的范数的影响。为了确保一致性并消除不同范数的潜在影响,我们还需要施加f的范数等于1的约束。为了得到范数条件下二次型的平稳值,我们利用了拉格朗日乘子法这一强大的优化技术。对该问题进行适当的变换,最终得到一个特征值问题:这个特征值提供了一个关系:L的每个特征值反映了图拉普拉斯的二次形的值。简单地说,这些特征值捕获了图形信号振动的频率。这样我们对特征值作为函数频率的指标有了基本的理解。特征向量和图拉普拉斯之间的联系成为进行图傅立叶变换的途径——一个系统地揭示图信号内在频率元素的过程。现在,我们可以看看傅里叶变换的定义了
从图傅里叶变换到图卷积
上面介绍的图傅里叶变换,我们获得了一个有效分析和处理图信号的强大工具。在我们研究图傅里叶变换和图卷积之间的联系。这种联系的核心是卷积定理,这个原理建立了傅里叶域中卷积运算和元素积之间的联系。卷积运算类似于傅里叶域中变换后的信号的逐元乘法。利用卷积定理可以推导图卷积的一个间接定义:
- 对图形信号进行傅里叶变换。
- 将变换后的信号与一个可学习的权重向量相乘。
- 对元素积进行傅里叶反变换,得到图卷积的输出。
图卷积的公式现在可以表述如下:为了使这个定义更加精简,我们引入了一个实用的参数化。由于与U*f的元素积可以表示为与diag(U*f)的积,s所以设可学习权值θ为:
通过利用这种参数化,gθ的图卷积公式采用了一种简化和直观的形式:
看看,我们已经从图的傅里叶变换中定义了一个图卷积!
总结
在本文中,我们从揭示图拉普拉斯的基本原理开始,然后深入研究了图卷积的基本概念,这是图傅里叶变换的推导。本文中所做的推到应该能够加深了你对图卷积本质的理解。
相关文章:

如何理解图神经网络的傅里叶变换和图卷积
图神经网络(GNN)代表了一类强大的深度神经网络架构。在一个日益互联的世界里,因为信息的联通性,大部分的信息可以被建模为图。例如,化合物中的原子是节点,它们之间的键是边。图神经网络的美妙之处在于它们能…...

国家网络安全周2023时间是什么时候?有什么特点?谁举办的?
国家网络安全周2023时间是什么时候? 2023年国家网络安全宣传周将于9月11日至17日在全国范围内统一开展。其中开幕式等重要活动将在福建省福州市举行。今年网安周期间,除开幕式外,还将举行网络安全博览会、网络安全技术高峰论坛、网络安全微视…...

windows编程之线程同步万字总结(创建线程,互斥对象,互斥事件,信号量,关键段,多线程群聊服务器)
文章目录 创建线程方法一_beginthreadex函数讲解使用示例: 方法二CreateThread函数讲解:使用示例: 互斥对象:创建互斥对象CreateMutex 互斥事件介绍创建或打开一个未命名的互斥事件对象 信号量介绍信号量的相关函数使用示例 关键段相关函数错误使用示例正确使用示例…...
Git在已有的项目中引入Submodule子模块管理:添加、更新、删除(实战示例代码)
前言 在进行Git版本控制的过程中,有时候我们需要在已有的项目中引入子模块,以便复用其他独立的Git存储库的代码或文件。本文将详细介绍如何在已有项目下添加、更新和删除Git的Submodule子模块,并提供相关的示例代码。 实战场景 假设我们已…...

内网穿透实现Windows远程桌面访问Ubuntu,简单高效的远程桌面解决方案
文章目录 前言1. ubuntu安装XRDP2.局域网测试连接3.安装cpolar内网穿透4.cpolar公网地址测试访问5.固定域名公网地址 前言 XRDP是一种开源工具,它允许用户通过Windows RDP访问Linux远程桌面。 除了Windows RDP外,xrdp工具还接受来自其他RDP客户端(如Fre…...
如何学习运营管理
运营管理(Operations Management)是一门管理学科,它关注如何高效地组织和管理企业的生产、服务、供应链和业务过程以达到组织的目标。运营管理是企业管理的一个重要领域,它包含了多个内容和职能: 生产管理:…...

腾讯云centos7.6安装部署备忘
1.Mysql 1.1 安装mysql wget http://dev.mysql.com/get/mysql-community-release-el7-5.noarch.rpm rpm -ivh mysql-community-release-el7-5.noarch.rpm yum install mysql-community-server 1.1.1 安装后重启 service mysqld restart 1.1.2 初次安装mysql,root账…...

【赠书活动】考研备考书单推荐
👉博__主👈:米码收割机 👉技__能👈:C/Python语言 👉公众号👈:测试开发自动化【获取源码商业合作】 👉荣__誉👈:阿里云博客专家博主、5…...

中缀表达式 - 栈实现综合计算器
代码: package Algotithm.stackobject Calculator {def main(args: Array[String]): Unit {val expression "32*6-2"//创建两个栈:数栈、符号栈val numStack, operStack new ArrayStack2(10)//定义需要的相关变量var index, num1, num2, …...
html语音播报功能问题
语音播报有个问题,就是弹出层有时无法关闭页面的播报,如果弹出层也有语音播报,就会造成语音混者播放 解决办法就是在弹出窗口(我用的弹出层框架是layui的)之前清空语音 window.operEdit function (url, title){window.speechSynthesis.can…...

计算机重点学科评级B-,山东省属重点高校考情分析
山东科技大学(B-) 考研难度(☆☆) 内容:23考情概况(拟录取和复试分析)、院校概况、23专业目录、23复试详情、各专业考情分析、各科目考情分析。 正文1175字预计阅读:3分钟 2023考情概况 山东科技大学计…...

轻松搭建本地知识库的ChatGLM2-6B
近期发现了一个项目,它的前身是ChatGLM,在我之前的博客中有关于ChatGLM的部署过程,本项目在前者基础上进行了优化,可以基于当前主流的LLM模型和庞大的知识库,实现本地部署自己的ChatGPT,并可结合自己的知识…...

flink的物理DataFlow图及Slot处理槽任务分配
背景 在flink中,有几个比较重要的概念,逻辑DataFlow图,物理DataFlow图以及处理槽执行任务,本文就来讲解下这几个概念 概念详解 假设有以下代码:数据源和统计单词算子的并行度是2,数据汇算子的并行度是1&…...
与面试相关的redis
这里写自定义目录标题 📝 redis的知识点数据结构及其特性,用途和操作方法持久化高可用分布式锁发布订阅性能优化安全性数据分片缓存策略键过期删除策略内存淘汰策略 🤗 总结归纳📎 参考文章 😀 这里写文章的前言&#…...
MapStruct从0到0.5
MapStruct从0到0.5 开发的过程,经常会用到实体类属性映射,同时为了方便,开发者也很少自己写专门的属性赋值工具类。索性会直接使用Sprrng提供的BeanUtils工具类,然后在性能上和字段属性赋值上的问题,一直是为开发者所…...

STM32H750 HAL CUBEMX 时钟失败及死机无法下载问题解决
芯片采样电压设置,否则 无法运行 解决死机问题 设置swd 模式 短接 boot0 —vcc 3.3v即可正常下载...

paddlespeech on centos7
概述 paddlespeech是百度飞桨平台的开源工具包,主要用于语音和音频的分析处理,其中包含多个可选模型,提供语音识别、语音合成、说话人验证、关键词识别、音频分类和语音翻译等功能。 paddlespeech整体是比较简单易用的,但是安装…...
ROM是什么? 刷ROM是什么意思?
文章目录 ROM是什么?刷ROM是什么意思 ROM是什么? ROM是只读内存(Read-Only Memory)的简称,是一种只能读出事先所存数据的固态半导体存储器。其特性是一旦储存资料就无法再将之改变或删除。通常用在不需经常变更资料的…...

华为云Stack的学习(五)
六、华为云stack服务简介 1.云服务在华为云Stack中的位置 云服务对接多个数据中心资源池层提供的资源,并向各种行业应用提供载体。 2.华为云Stack通用服务 2.1 云计算的服务模式 2.2 计算相关的云服务 2.3 存储相关的云服务 2.4 网络相关的云服务 3.云化案例 **…...

【LeetCode-中等题】904. 水果成篮
文章目录 题目方法一:滑动窗口方法二: 题目 题目的意思就是:找至多包含两种元素的最长子串,返回其长度 方法一:滑动窗口 class Solution { // 滑动窗口 找至多包含两种元素的最长子串,返回其长度public …...

linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...

Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...